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

DOI10.1016/j.tcs.2020.03.010zbMath1437.05200OpenAlexW3013892856MaRDI QIDQ2173303

Hyeong-Seok Lim, Jung-Heum Park

Publication date: 22 April 2020

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

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

zbMATH Keywords

interval graphsdisjoint pathpath coverpath partitionscattering number\(r\)-scattering number

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Paired 2-disjoint path covers of multi-dimensional torus networks with \(2n-3\) faulty edges
• Ore-type degree conditions for disjoint path covers in simple graphs
• 1-tough cocomparability graphs are hamiltonian
• Proper interval graphs and the guard problem
• Measuring the vulnerability for classes of intersection graphs
• A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph
• One-to-one disjoint path covers in digraphs
• The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
• Disjoint path covers joining prescribed source and sink sets in interval graphs
• Scattering number in graphs
• On Path Cover Problems in Digraphs and Applications to Program Testing
• Computing the Scattering Number of Graphs
• 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
• Necklaces, Convolutions, and X + Y
• A Characterization of Comparability Graphs and of Interval Graphs

This page was built for publication: Characterization of interval graphs that are unpaired 2-disjoint path coverable