An optimal path cover algorithm for cographs
From MaRDI portal
Publication:1903198
DOI10.1016/0898-1221(95)00139-PzbMath0836.68086MaRDI QIDQ1903198
Publication date: 26 November 1995
Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)
Related Items (27)
Algorithms for finding disjoint path covers in unit interval graphs ⋮ Computing directed Steiner path covers ⋮ On the \(k\)-path cover problem for cacti ⋮ A faster parallel connectivity algorithm on cographs ⋮ 1-tough cocomparability graphs are hamiltonian ⋮ A simple linear time algorithm to solve the MIST problem on interval graphs ⋮ Disjoint path covers with path length constraints in restricted hypercube-like graphs ⋮ The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs ⋮ A time-optimal solution for the path cover problem on cographs. ⋮ On the \(k\)-path partition of graphs. ⋮ Complexity results on cosecure domination in graphs ⋮ An optimal algorithm for the \(k\)-fixed-endpoint path cover on proper interval graphs ⋮ Algorithmic aspects of switch cographs ⋮ The 1-fixed-endpoint path cover problem is Polynomial on interval graphs ⋮ Path covering number and \(L(2,1)\)-labeling number of graphs ⋮ A linear algorithm for the Hamiltonian completion number of the line graph of a cactus. ⋮ Computing Directed Steiner Path Covers for Directed Co-graphs (Extended Abstract) ⋮ Finding a minimum path cover of a distance-hereditary graph in polynomial time ⋮ The harmonious coloring problem is NP-complete for interval and permutation graphs ⋮ Local search algorithms for finding the Hamiltonian completion number of line graphs ⋮ Path partition for graphs with special blocks ⋮ On characterizations for subclasses of directed co-graphs ⋮ Hamiltonicity in graphs with few \(P_ 4\)'s ⋮ Efficient parallel recognition of cographs ⋮ The approximability of the weighted Hamiltonian path completion problem on a tree ⋮ Algorithms for maximum internal spanning tree problem for some graph classes ⋮ Solving the path cover problem on circular-arc graphs by using an approximation algorithm
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complement reducible graphs
- A tree representation for \(P_ 4\)-sparse graphs
- On a class of posets and the corresponding comparability graphs
- On a property of the class of n-colorable graphs
- P4-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
- A Linear Recognition Algorithm for Cographs
- Dacey Graphs
- AN EFFICIENT EREW ALGORITHM FOR MINIMUM PATH COVER AND HAMILTONICITY ON COGRAPHS
This page was built for publication: An optimal path cover algorithm for cographs
