The 1-fixed-endpoint path cover problem is Polynomial on interval graphs

DOI10.1007/s00453-009-9292-5zbMath1200.05212OpenAlexW2023957019MaRDI QIDQ1957649

Stavros D. Nikolopoulos, Katerina Asdre

Publication date: 27 September 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.216.7769

zbMATH Keywords

Linear-time algorithmsInterval graphsPerfect graphsFixed-endpoint path coverPath cover

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (23)

Algorithms for finding disjoint path covers in unit interval graphs ⋮ Paired many-to-many disjoint path covers in restricted hypercube-like graphs ⋮ A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph ⋮ Disjoint path covers with path length constraints in restricted hypercube-like graphs ⋮ Characterization of interval graphs that are unpaired 2-disjoint path coverable ⋮ Disjoint path covers joining prescribed source and sink sets in interval graphs ⋮ Unpaired Many-to-Many Disjoint Path Cover of Balanced Hypercubest ⋮ The longest path problem is polynomial on cocomparability graphs ⋮ Ore-type degree conditions for disjoint path covers in simple graphs ⋮ Paired 3-Disjoint Path Covers in Bipartite Torus-Like Graphs with Edge Faults ⋮ One-to-one disjoint path covers in digraphs ⋮ A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs ⋮ Unpaired many-to-many disjoint path covers in restricted hypercube-like graphs ⋮ The longest path problem has a polynomial solution on interval graphs ⋮ Flow shop scheduling problem with conflict graphs ⋮ Many-to-many two-disjoint path covers in restricted hypercube-like graphs ⋮ Single-source three-disjoint path covers in cubes of connected graphs ⋮ Torus-like graphs and their paired many-to-many disjoint path covers ⋮ Paired 2-disjoint path covers and strongly Hamiltonian laceability of bipartite hypercube-like graphs ⋮ The Longest Path Problem is Polynomial on Cocomparability Graphs ⋮ Many-to-many two-disjoint path covers in cylindrical and toroidal grids ⋮ Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs ⋮ The unpaired many-to-many \(k\)-disjoint paths in bipartite hypercube-like networks

Cites Work

• Unnamed Item
• Unnamed Item
• Linear algorithm for optimal path cover problem on interval graphs
• Finding Hamiltonian circuits in proper interval graphs
• Finding Hamiltonian circuits in interval graphs
• Hamiltonian circuits in interval graph generalizations
• A unified approach to domination problems on interval graphs
• The directed subgraph homeomorphism problem
• Disjoint paths in graphs
• 2-linked graphs
• Paths in interval graphs and circular arc graphs
• Optimal path cover problem on block graphs and bipartite permutation graphs
• A time-optimal solution for the path cover problem on cographs.
• Parallel algorithms for Hamiltonian problems on quasi-threshold graphs
• An efficient parallel strategy for the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs
• Graph minors. XIII: The disjoint paths problem
• An optimal path cover algorithm for cographs
• HAMILTONian circuits in chordal bipartite graphs
• The Hamiltonian problem on distance-hereditary graphs
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• Solving the path cover problem on circular-arc graphs by using an approximation algorithm
• ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES
• A Polynomial Solution to the Undirected Two Paths Problem
• On the Computational Complexity of Combinatorial Problems
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Graph Classes: A Survey
• Computing and Combinatorics
• A linear‐time algorithm for the k‐fixed‐endpoint path cover problem on cographs

This page was built for publication: The 1-fixed-endpoint path cover problem is Polynomial on interval graphs