Approximating the path-distance-width for AT-free graphs and graphs in related classes
DOI10.1016/j.dam.2012.11.015zbMath1285.05048OpenAlexW2031276298MaRDI QIDQ2442209
Yushi Uno, Yoshio Okamoto, Katsuhisa Yamanaka, Hirotaka Ono, Toshiki Saitoh, Koichi Yamazaki, Shuji Kijima, Yota Otachi
Publication date: 2 April 2014
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2012.11.015
Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bandwidth on AT-free graphs
- Simple linear time recognition of unit interval graphs
- Distances in cocomparability graphs and their powers
- On finding the minimum bandwidth of interval graphs
- Isomorphism for graphs of bounded distance width
- Characterizations and algorithmic applications of chordal graph embeddings
- On claw-free asteroidal triple-free graphs
- Computing the Bandwidth of Interval Graphs
- An ${\mathcal{O}}(n^2)$ -time Algorithm for the Minimal Interval Completion Problem
- 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
This page was built for publication: Approximating the path-distance-width for AT-free graphs and graphs in related classes
