Approximability of the Path-Distance-Width for AT-free Graphs

DOI10.1007/978-3-642-25870-1_25zbMath1341.05054OpenAlexW110470963MaRDI QIDQ3104783

Toshiki Saitoh, Yoshio Okamoto, Koichi Yamazaki, Katsuhisa Yamanaka, Hirotaka Ono, Shuji Kijima, Yota Otachi, Yushi Uno

Publication date: 16 December 2011

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-25870-1_25

zbMATH Keywords

AT-free graphsinterval graphs\(k\)-cocomparability graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simple linear time recognition of unit interval graphs
• On finding the minimum bandwidth of interval graphs
• Isomorphism for graphs of bounded distance width
• Characterizations and algorithmic applications of chordal graph embeddings
• Computing the Bandwidth of Interval Graphs
• Bandwidth on AT-Free Graphs
• The NP-completeness column: an ongoing guide
• Graph Classes: A Survey
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
• Asteroidal Triple-Free Graphs
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• On approximation intractability of the path-distance-width problem