Algorithms for finding disjoint path covers in unit interval graphs

DOI10.1016/J.DAM.2015.12.002MaRDI QIDQ266951zbMATH OpenOpenAlexFDO

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

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

disjoint pathgraph algorithmpath 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)

Recommendations

• Covering a graph with nontrivial vertex-disjoint paths: existence and optimization
• Approximation algorithms for covering a graph by vertex-disjoint paths of maximum total weight
• scientific article; zbMATH DE number 1151806
• Algorithms for finding biclique covers of graphs with bounded pathwidth
• Exact algorithms for finding partial edge-disjoint paths
• scientific article; zbMATH DE number 780786
• Linear algorithm for optimal path cover problem on interval graphs
• A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
• Characterization of interval graphs that are unpaired 2-disjoint path coverable

Cites work

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

Cited in

(8)

• Covering a graph with nontrivial vertex-disjoint paths: existence and optimization
• A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph
• Characterization of interval graphs that are unpaired 2-disjoint path coverable
• Torus-like graphs and their paired many-to-many disjoint path covers
• Disjoint path covers with path length constraints in restricted hypercube-like graphs
• Disjoint path covers joining prescribed source and sink sets in interval graphs
• A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
• On the unit interval graphs which are paired k-disjoint path coverable

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q266951)