An optimal algorithm for the \(k\)-fixed-endpoint path cover on proper interval graphs
DOI10.1007/s11786-009-0004-yzbMath1205.05226OpenAlexW2147102683MaRDI QIDQ626964
Walter Unger, George B. Mertzios
Publication date: 19 February 2011
Published in: Mathematics in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s11786-009-0004-y
Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Simple linear time recognition of unit interval graphs
- Linear algorithm for optimal path cover problem on interval graphs
- A linear time recognition algorithm for proper interval graphs
- Hamiltonian circuits in interval graph generalizations
- An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
- Paths in interval graphs and circular arc graphs
- Optimal path cover problem on block graphs and bipartite permutation graphs
- Algorithmic graph theory and perfect graphs
- An optimal path cover algorithm for cographs
- HAMILTONian circuits in chordal bipartite graphs
- A matrix characterization of interval and proper interval graphs
- Solving the path cover problem on circular-arc graphs by using an approximation algorithm
- A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
- Efficient algorithms for interval graphs and circular-arc graphs
- The Planar Hamiltonian Circuit Problem is NP-Complete
- A linear‐time algorithm for the k‐fixed‐endpoint path cover problem on cographs
This page was built for publication: An optimal algorithm for the \(k\)-fixed-endpoint path cover on proper interval graphs
