Name
Title | ||
|---|---|---|
Approximating the path-distance-width for AT-free graphs and graphs in related classes. |
Abstract | ||
|---|---|---|
We consider the problem of determining the path-distance-width for AT-free graphs and graphs in related classes such as k-cocomparability graphs, proper interval graphs, cobipartite graphs, and cochain graphs. We first show that the problem is NP-hard even for cobipartite graphs, and thus for AT-free graphs. Next we present simple approximation algorithms with constant approximation ratios for AT-free graphs and graphs in the related graph classes mentioned above. 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 cochain graphs, which form a subclass of the class of proper interval graphs. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.dam.2012.11.015 | Discrete Applied Mathematics |
Keywords | Field | DocType |
linear time,at-free graph,polynomial time,related class,approximation factor,simple approximation algorithm,proper interval graph,cochain graph,cobipartite graph,constant approximation ratio,approximation algorithm | Discrete mathematics,Modular decomposition,Indifference graph,Combinatorics,Clique-sum,Chordal graph,Pathwidth,Longest path problem,1-planar graph,Mathematics,Maximal independent set | Journal |
Volume | ISSN | Citations |
168 | 0166-218X | 1 |
PageRank | References | Authors |
0.35 | 17 | 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 |