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

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

Keywords

  • IR-92410
  • METIS-140797

Cite this