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

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)


The path-distance-width of a graph measures how close the graph is to a path. We consider the problem of determining the path-distance-width for graphs with chain-like structures such as k-cocomparability graphs, AT-free graphs, and interval graphs. We first show that the problem is NP-hard even for a very restricted subclass of AT-free graphs. Next we present simple approximation algorithms with constant approximation ratios for graphs with chain-like structures. For instance, our algorithm for AT-free graphs has approximation factor 3 and runs in linear time. We also show that the problem is solvable in polynomial time for the class of cochain graphs, which is a subclass of the class of proper interval graphs.

Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers
Number of pages12
Publication statusPublished - 2011
Event37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011 - Tepla Monastery, Czech Republic
Duration: Jun 21 2011Jun 24 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6986 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011
Country/TerritoryCzech Republic
CityTepla Monastery

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Approximability of the path-distance-width for AT-free graphs'. Together they form a unique fingerprint.

Cite this