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

A.J.J. Kloks; Ton Kloks; Dieter Kratsch; Jeremy Spinrad

doi:10.1016/S0304-3975(96)00206-X

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

A.J.J. Kloks, Ton Kloks, Dieter Kratsch, Jeremy Spinrad

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

68 Citations (Scopus)

190 Downloads (Pure)

Abstract

We present O(n5R + n3R3) 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 ⩾ 1.

Original language	Undefined
Pages (from-to)	309-335
Number of pages	25
Journal	Theoretical computer science
Volume	175
Issue number	2
DOIs	https://doi.org/10.1016/S0304-3975(96)00206-X
Publication status	Published - 1997

Keywords

IR-92410
METIS-140797

Access to Document

10.1016/S0304-3975(96)00206-X

1-s2.0-S030439759600206X-main

Cite this

@article{fa6f38dd47b64e0d94f22344aaa52aff,

title = "On treewidth and minimum fill-in of asteroidal triple-free graphs",

abstract = "We present O(n5R + n3R3) 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 ⩾ 1.",

keywords = "IR-92410, METIS-140797",

author = "A.J.J. Kloks and Ton Kloks and Dieter Kratsch and Jeremy Spinrad",

year = "1997",

doi = "10.1016/S0304-3975(96)00206-X",

language = "Undefined",

volume = "175",

pages = "309--335",

journal = "Theoretical computer science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

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

AU - Kloks, A.J.J.

AU - Kloks, Ton

AU - Kratsch, Dieter

AU - Spinrad, Jeremy

PY - 1997

Y1 - 1997

N2 - We present O(n5R + n3R3) 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 ⩾ 1.

AB - We present O(n5R + n3R3) 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 ⩾ 1.

KW - IR-92410

KW - METIS-140797

U2 - 10.1016/S0304-3975(96)00206-X

DO - 10.1016/S0304-3975(96)00206-X

M3 - Article

SN - 0304-3975

VL - 175

SP - 309

EP - 335

JO - Theoretical computer science

JF - Theoretical computer science

IS - 2

ER -