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




Related Items (23)

Algorithms for finding disjoint path covers in unit interval graphsPaired many-to-many disjoint path covers in restricted hypercube-like graphsA linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graphDisjoint path covers with path length constraints in restricted hypercube-like graphsCharacterization of interval graphs that are unpaired 2-disjoint path coverableDisjoint path covers joining prescribed source and sink sets in interval graphsUnpaired Many-to-Many Disjoint Path Cover of Balanced HypercubestThe longest path problem is polynomial on cocomparability graphsOre-type degree conditions for disjoint path covers in simple graphsPaired 3-Disjoint Path Covers in Bipartite Torus-Like Graphs with Edge FaultsOne-to-one disjoint path covers in digraphsA Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval GraphsUnpaired many-to-many disjoint path covers in restricted hypercube-like graphsThe longest path problem has a polynomial solution on interval graphsFlow shop scheduling problem with conflict graphsMany-to-many two-disjoint path covers in restricted hypercube-like graphsSingle-source three-disjoint path covers in cubes of connected graphsTorus-like graphs and their paired many-to-many disjoint path coversPaired 2-disjoint path covers and strongly Hamiltonian laceability of bipartite hypercube-like graphsThe Longest Path Problem is Polynomial on Cocomparability GraphsMany-to-many two-disjoint path covers in cylindrical and toroidal gridsLinear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval GraphsThe unpaired many-to-many \(k\)-disjoint paths in bipartite hypercube-like networks



Cites Work


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