Name
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-25870-1_25 | WG |
Keywords | Field | DocType |
k-cocomparability graph,simple approximation algorithm,constant approximation ratio,interval graph,chain-like structure,approximation factor,at-free graph,graph measure,linear time,cochain graph | Discrete mathematics,Indifference graph,Combinatorics,Chordal graph,Cograph,Graph product,Pathwidth,Longest path problem,1-planar graph,Mathematics,Maximal independent set | Conference |
Volume | ISSN | Citations |
6986 | 0302-9743 | 2 |
PageRank | References | Authors |
0.39 | 16 | 8 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yota Otachi | 1 | 161 | 37.16 |
| Toshiki Saitoh | 2 | 87 | 14.95 |
| Katsuhisa Yamanaka | 3 | 60 | 15.73 |
| Shuji Kijima | 4 | 181 | 23.04 |
| Yoshio Okamoto | 5 | 15 | 2.71 |
| Hirotaka Ono | 6 | 400 | 56.98 |
| yushi uno | 7 | 222 | 28.80 |
| Koichi Yamazaki | 8 | 222 | 21.85 |