| 中文摘要 |
Let G = (V, E) be a graph with vertex set V and edge set E and let T be a subset of V. A terminal path cover PC of G with respect to T is a set of pairwise vertex-disjoint paths of G which cover the vertices of G such that all vertices in T are end vertices of paths in PC. The terminal path cover problem is to find a terminal path cover of G of minimum cardinality with respect to T. The path cover problem is a special case of the terminal path cover problem with T be empty. A graph is a cograph if it can be described by expressions involving operations of merging disjoint graphs and taking complements of graphs. Cographs have arisen in many different areas of applied mathematics and computer science and have been independently rediscovered by various researchers. In this paper, we show that the terminal path cover problem on cographs can be solved in linear time. |
本站僅提供期刊文獻檢索。
