Algorithms for finding disjoint path covers in unit interval graphs

DOI10.1016/j.dam.2015.12.002zbMath1333.05296OpenAlexW2281046621MaRDI QIDQ266951

Jung-Heum Park, Hyeong-Seok Lim, Joonsoo Choi

Publication date: 7 April 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.12.002

zbMATH Keywords

graph algorithmdisjoint pathpath coverpath partitionproper interval graph

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 (3)

Disjoint path covers with path length constraints in restricted hypercube-like graphs ⋮ Disjoint path covers joining prescribed source and sink sets in interval graphs ⋮ Torus-like graphs and their paired many-to-many disjoint path covers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Many-to-many disjoint path covers in \(k\)-ary \(n\)-cubes
• Paired many-to-many disjoint path covers in faulty hypercubes
• Paired 2-disjoint path covers and strongly Hamiltonian laceability of bipartite hypercube-like graphs
• One-to-one disjoint path covers on \(k\)-ary \(n\)-cubes
• Disjoint path covers in recursive circulants \(G(2^m,4)\) with faulty elements
• Simple linear time recognition of unit interval graphs
• Many-to-many disjoint paths in faulty hypercubes
• Linear algorithm for optimal path cover problem on interval graphs
• Path partitions of hypercubes
• Finding Hamiltonian circuits in proper interval graphs
• The directed subgraph homeomorphism problem
• Optimal path cover problem on block graphs and bipartite permutation graphs
• Proper interval graphs and the guard problem
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Algorithmic graph theory and perfect graphs
• Graph minors. XIII: The disjoint paths problem
• An optimal path cover algorithm for cographs
• The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
• A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs
• Many-to-many two-disjoint path covers in cylindrical and toroidal grids
• Optimal greedy algorithms for indifference graphs
• Many-to-many two-disjoint path covers in restricted hypercube-like graphs
• Single-source three-disjoint path covers in cubes of connected graphs
• Paired many-to-many disjoint path covers of the hypercubes
• Disjoint path covers in cubes of connected graphs
• Finding a minimum path cover of a distance-hereditary graph in polynomial time
• On the compatibility between a graph and a simple order
• Partitions of Faulty Hypercubes into Paths with Prescribed Endvertices
• Embedding $m$-quasistars into $n$-cubes
• A Polynomial Solution to the Undirected Two Paths Problem
• On Path Cover Problems in Digraphs and Applications to Program Testing
• General-demand disjoint path covers in a graph with faulty elements
• Many-to-Many Disjoint Path Covers in the Presence of Faulty Elements
• Paired Many-to-Many Disjoint Path Covers in Recursive Circulants $(G(2^m,4))$
• Disjoint paths in hypercubes with prescribed origins and lengths

This page was built for publication: Algorithms for finding disjoint path covers in unit interval graphs