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

doi:10.1007/978-3-642-25870-1_25

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 proceeding › Conference contribution

2 Citations (Scopus)

Abstract

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 language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers
Pages	271-282
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-25870-1_25
Publication status	Published - 2011
Event	37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011 - Tepla Monastery, Czech Republic Duration: Jun 21 2011 → Jun 24 2011

Publication series

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

Other

Other	37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011
Country/Territory	Czech Republic
City	Tepla Monastery
Period	6/21/11 → 6/24/11

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-25870-1_25

Cite this

Otachi, Y., Saitoh, T., Yamanaka, K., Kijima, S., Okamoto, Y., Ono, H., Uno, Y., & Yamazaki, K. (2011). Approximability of the path-distance-width for AT-free graphs. In Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers (pp. 271-282). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6986 LNCS). https://doi.org/10.1007/978-3-642-25870-1_25

Approximability of the path-distance-width for AT-free graphs. / Otachi, Yota; Saitoh, Toshiki; Yamanaka, Katsuhisa et al.
Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers. 2011. p. 271-282 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6986 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Otachi, Y, Saitoh, T, Yamanaka, K, Kijima, S, Okamoto, Y, Ono, H, Uno, Y & Yamazaki, K 2011, Approximability of the path-distance-width for AT-free graphs. in Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6986 LNCS, pp. 271-282, 37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011, Tepla Monastery, Czech Republic, 6/21/11. https://doi.org/10.1007/978-3-642-25870-1_25

Otachi Y, Saitoh T, Yamanaka K, Kijima S, Okamoto Y, Ono H et al. Approximability of the path-distance-width for AT-free graphs. In Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers. 2011. p. 271-282. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-25870-1_25

Otachi, Yota ; Saitoh, Toshiki ; Yamanaka, Katsuhisa et al. / Approximability of the path-distance-width for AT-free graphs. Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers. 2011. pp. 271-282 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1d9209c03aa040fb8ab32a171935b69b,

title = "Approximability of the path-distance-width for AT-free graphs",

abstract = "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.",

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

year = "2011",

doi = "10.1007/978-3-642-25870-1_25",

language = "English",

isbn = "9783642258695",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "271--282",

booktitle = "Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers",

note = "37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011 ; Conference date: 21-06-2011 Through 24-06-2011",

}

TY - GEN

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

AU - Otachi, Yota

AU - Saitoh, Toshiki

AU - Yamanaka, Katsuhisa

AU - Kijima, Shuji

AU - Okamoto, Yoshio

AU - Ono, Hirotaka

AU - Uno, Yushi

AU - Yamazaki, Koichi

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84855408658&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84855408658&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-25870-1_25

DO - 10.1007/978-3-642-25870-1_25

M3 - Conference contribution

AN - SCOPUS:84855408658

SN - 9783642258695

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 271

EP - 282

BT - Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers

T2 - 37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011

Y2 - 21 June 2011 through 24 June 2011

ER -

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

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this