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 条
  • [1] COMPLEXITY OF FINDING EMBEDDINGS IN A K-TREE
    ARNBORG, S
    CORNEIL, DG
    PROSKUROWSKI, A
    [J]. SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1987, 8 (02): : 277 - 284
  • [2] BODLAENDER H, 1996, UNPUB TREEWIDTH MINI
  • [3] Bodlaender H. L., 1993, Acta Cybernetica, V11, P1
  • [4] TREEWIDTH AND PATHWIDTH OF PERMUTATION GRAPHS
    BODLAENDER, HL
    KLOKS, T
    KRATSCH, D
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 1995, 8 (04) : 606 - 616
  • [5] Corneil D.G., 1994, LECT NOTES COMPUTER, V790, P211
  • [6] Corneil DG, 1995, LECT NOTES COMPUT SC, V944, P292
  • [7] Dirac G. A., 1961, Abh. Math. Semin. Univ. Hambg, V25, P71, DOI DOI 10.1007/BF02992776
  • [8] Golumbic MC., 1980, Algorithmic Graph Theory and Perfect Graphs
  • [9] TREE-WIDTH OF COCOMPARABILITY GRAPHS AND A NEW ORDER THEORETIC PARAMETER
    HABIB, M
    MOHRING, RH
    [J]. ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1994, 11 (01): : 47 - 60
  • [10] Kloks T., 1994, Treewidth. Computations and approximations, DOI 10.1007/BFb0045375
123