On treewidth and minimum fill-in of asteroidal triple-free graphs

被引：55
作者：
Kloks, T
Kratsch, D
Spinrad, J
机构：
[1] IRISA,RENNES,FRANCE
[2] UNIV JENA,FAK MATH & INFORMAT,D-07740 JENA,GERMANY
[3] VANDERBILT UNIV,DEPT COMP SCI,NASHVILLE,TN 37235
来源：
THEORETICAL COMPUTER SCIENCE | 1997年 / 175卷 / 02期
关键词：
D O I：
10.1016/S0304-3975(96)00206-X
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We present O(n(5)R + n(3)R(3)) time algorithms to compute the treewidth, pathwidth, minimum fill-in and minimum interval graph completion of asteroidal triple-free graphs, where n is the number of vertices and R is the number of minimal separators of the input graph. This yields polynomial time algorithms for the four NP-complete graph problems on any subclass of the asteroidal triple-free graphs that has a polynomially bounded number of minimal separators, as e.g. cocomparability graphs of bounded dimension and d-trapezoid graphs for any fixed d greater than or equal to 1.
引用
收藏
页码：309 / 335
页数：27
相关论文
共 24 条
  • [11] KLOKS T, 1994, LECT NOTES COMPUTER, V775, P759
  • [12] KLOKS T, 1995, LECT NOTES COMPUTER, V979, P434
  • [13] KLOKS T, IN PRESS SIAM J COMP
  • [14] Kratsch D., 1996, THESIS F SCHILLER U
  • [15] Triangulating graphs without asteroidal triples
    Mohring, RH
    [J]. DISCRETE APPLIED MATHEMATICS, 1996, 64 (03) : 281 - 287
  • [16] Ohtsuki T., 1976, SIAM Journal on Computing, V5, P133, DOI 10.1137/0205012
  • [17] PARRA A, 1995, LECT NOTES COMPUTER, V944, P13
  • [18] Rose D. J., 1976, SIAM Journal on Computing, V5, P266, DOI 10.1137/0205021
  • [19] Rose D. J., 1970, Journal of Mathematical Analysis and Applications, V32, P597, DOI 10.1016/0022-247X(70)90282-9
  • [20] ON COMPARABILITY AND PERMUTATION GRAPHS
    SPINRAD, J
    [J]. SIAM JOURNAL ON COMPUTING, 1985, 14 (03) : 658 - 670
123