The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
From MaRDI portal
Publication:1957649
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
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