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

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

Research output: Contribution to journalArticleAcademicpeer-review

67 Citations (Scopus)
119 Downloads (Pure)


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 languageUndefined
Pages (from-to)309-335
Number of pages25
JournalTheoretical computer science
Issue number2
Publication statusPublished - 1997


  • IR-92410
  • METIS-140797

Cite this