Disjoint path covers joining prescribed source and sink sets in interval graphs

DOI10.1016/j.tcs.2019.01.019zbMath1425.05083OpenAlexW2912114731WikidataQ128589653 ScholiaQ128589653MaRDI QIDQ2419125

Hyeong-Seok Lim, Jae-Hoon Kim, Jung-Heum Park

Publication date: 29 May 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2019.01.019

zbMATH Keywords

fault tolerancedisjoint pathpath coverpath partitionscattering number

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (1)

Characterization of interval graphs that are unpaired 2-disjoint path coverable

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms for finding disjoint path covers in unit interval graphs
• Paired many-to-many disjoint path covers in faulty hypercubes
• Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
• Disjoint path covers in recursive circulants \(G(2^m,4)\) with faulty elements
• A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph
• Ore-type degree conditions for disjoint path covers in simple graphs
• Linear algorithm for optimal path cover problem on interval graphs
• Finding Hamiltonian circuits in interval graphs
• Paths in interval graphs and circular arc graphs
• On a class of posets and the corresponding comparability graphs
• 1-tough cocomparability graphs are hamiltonian
• The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
• Many-to-many two-disjoint path covers in cylindrical and toroidal grids
• Paired many-to-many disjoint path covers of the hypercubes
• Scattering number in graphs
• A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
• Partitions of Faulty Hypercubes into Paths with Prescribed Endvertices
• 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
• Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs
• Paired Many-to-Many Disjoint Path Covers in Recursive Circulants $(G(2^m,4))$
• A Characterization of Comparability Graphs and of Interval Graphs

This page was built for publication: Disjoint path covers joining prescribed source and sink sets in interval graphs