Approximability of the path-distance-width for AT-free graphs

DOI10.1007/978-3-642-25870-1_25MaRDI QIDQ3104783zbMATH OpenOpenAlexFDO

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

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

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

Mathematics Subject Classification ID

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

Recommendations

• Approximating the path-distance-width for AT-free graphs and graphs in related classes
• On approximation intractability of the path-distance-width problem
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Approximating the pathwidth of outerplanar graphs
• scientific article; zbMATH DE number 1696522

Cites work

• An O( n \log n ) Algorithm for Bandwidth of Interval Graphs
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Asteroidal Triple-Free Graphs
• Bandwidth on AT-free graphs
• Characterizations and algorithmic applications of chordal graph embeddings
• Computing the Bandwidth of Interval Graphs
• Graph Classes: A Survey
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2191988 (Why is no real title available?)
• Isomorphism for graphs of bounded distance width
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• On approximation intractability of the path-distance-width problem
• On finding the minimum bandwidth of interval graphs
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• Simple linear time recognition of unit interval graphs
• The NP-completeness column: an ongoing guide

Cited in

(3)

• Approximating the treewidth of AT-free graphs.
• Approximating the path-distance-width for AT-free graphs and graphs in related classes
• On approximation intractability of the path-distance-width problem

This page was built for publication: Approximability of the path-distance-width for AT-free graphs

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