Approximating the path-distance-width for AT-free graphs and graphs in related classes
Approximating the path-distance-width for AT-free graphs and graphs in related classes
复制标题
近似无 AT 图和相关类中的图的路径距离宽度
DOI：
10.1016/j.dam.2012.11.015
复制
发表时间：
2013
影响因子：
1.1
通讯作者：
and Koichi Yamazaki
中科院分区：
文献类型：
--
作者：
Yota Otachi;Toshiki Saitoh;Katsuhisa Yamanaka;Shuji Kijima;Yoshio Okamoto;Hirotaka Ono;Yushi Uno;and Koichi Yamazaki
我们考虑的问题，确定的路径距离宽度的AT-自由图和图在相关的类，如k-协可比图，适当的区间图，cobipartite图，和cochain图。我们首先表明，这个问题是NP-困难的，即使是cobipartite图，因此AT-自由图。接下来，我们提出了简单的近似算法与AT-自由图和图在上述相关的图形类的常数近似比。例如，我们的算法AT-自由图的近似因子3和运行在线性时间。我们还表明，这个问题是可解的多项式时间的上链图，形成一个子类的适当的区间图。
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.
登录
查看更多内容
关于无爪小行星三自由图
DOI：
10.1016/s0166-218x(01)00208-6
发表时间：
1999
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
Harald Hempel;D. Kratsch
通讯作者：
D. Kratsch
影响因子：
1.1
作者：
K. Yamazaki;H. Bodlaender;B. D. Fluiter;D. Thilikos
通讯作者：
D. Thilikos
DOI：
--
发表时间：
1997
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Gunter Blache;Marek Karpinski;J. Wirtgen
通讯作者：
J. Wirtgen
影响因子：
0.8
作者：
G. Khosrovshahi;S. Ajoodani
通讯作者：
S. Ajoodani
DOI：
10.1006/jagm.1998.0997
发表时间：
1995
期刊：
J. Algorithms
影响因子：
--
作者：
T. Kloks;D. Kratsch;H. Müller
通讯作者：
H. Müller