A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph

DOI10.1016/j.ipl.2018.10.010zbMath1469.68076OpenAlexW2896810482WikidataQ129038309 ScholiaQ129038309MaRDI QIDQ1628689

Insung Ihm, Jung-Heum Park

Publication date: 5 December 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2018.10.010

zbMATH Keywords

graph algorithmsdisjoint path covercube of graph

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (2)

Characterization of interval graphs that are unpaired 2-disjoint path coverable ⋮ Paired 3-Disjoint Path Covers in Bipartite Torus-Like Graphs with Edge Faults

Uses Software

• Algorithm 447

Cites Work

• Unnamed Item
• Generalized Gray codes with prescribed ends
• A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph
• Paired 2-disjoint path covers of multidimensional torus networks with faulty edges
• Computing roots of graphs is hard
• The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
• Linear-time algorithms for tree root problems
• Single-source three-disjoint path covers in cubes of connected graphs
• Disjoint path covers in cubes of connected graphs
• On Path Cover Problems in Digraphs and Applications to Program Testing
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Algorithms for Square Roots of Graphs
• Many-to-Many Disjoint Path Covers in the Presence of Faulty Elements
• On the Cube of a Graph

This page was built for publication: A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph