Computing treewidth and minimum fill-in: All you need are the minimal separators

T. Kloks; H. Bodlaender; H. Müller; D. Kratsch

doi:10.1007/3-540-57273-2_61

Computing treewidth and minimum fill-in: All you need are the minimal separators

T. Kloks, H. Bodlaender, H. Müller, D. Kratsch

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

Abstract

Consider a class of graphs G having a polynomial time algorithm computing the set of all minimal separators for every graph in G . We show that there is a polynomial time algorithm for treewidth and minimum fill-in, respectively, when restricted to the class G . Many interesting classes of intersection graphs have a polynomial time algorithm computing all minimal separators, like permutation graphs, circle graphs, circular arc graphs, distance hereditary graphs, chordal bipartite graphs etc. Our result generalizes earlier results for the treewidth and minimum fill-in for several of these classes. We also consider the related problems pathwidth and interval completion when restricted to some special graph classes.

Original language	English
Title of host publication	Algorithms—ESA '93
Subtitle of host publication	First Annual European Symposium Bad Honnef, Germany September 30–October 2, 1993 Proceedings
Editors	Thomas Lengauer
Publisher	Springer
Pages	260-271
Number of pages	12
Volume	726
ISBN (Electronic)	978-3-540-48032-7
ISBN (Print)	978-3-540-57273-2
DOIs	https://doi.org/10.1007/3-540-57273-2_61
Publication status	Published - 1993

Publication series

Name	Lecture Notes in Computer Science

Access to Document

10.1007/3-540-57273-2_61

http://dx.doi.org/10.1007/3-540-57273-2_61

Cite this

Kloks, T., Bodlaender, H., Müller, H., & Kratsch, D. (1993). Computing treewidth and minimum fill-in: All you need are the minimal separators. In T. Lengauer (Ed.), Algorithms—ESA '93: First Annual European Symposium Bad Honnef, Germany September 30–October 2, 1993 Proceedings (Vol. 726, pp. 260-271). (Lecture Notes in Computer Science). Springer. https://doi.org/10.1007/3-540-57273-2_61

@inbook{ed3d631bfd084a35a8c87d1c95124ce5,

title = "Computing treewidth and minimum fill-in: All you need are the minimal separators",

abstract = "Consider a class of graphs G having a polynomial time algorithm computing the set of all minimal separators for every graph in G . We show that there is a polynomial time algorithm for treewidth and minimum fill-in, respectively, when restricted to the class G . Many interesting classes of intersection graphs have a polynomial time algorithm computing all minimal separators, like permutation graphs, circle graphs, circular arc graphs, distance hereditary graphs, chordal bipartite graphs etc. Our result generalizes earlier results for the treewidth and minimum fill-in for several of these classes. We also consider the related problems pathwidth and interval completion when restricted to some special graph classes.",

author = "T. Kloks and H. Bodlaender and H. M{\"u}ller and D. Kratsch",

year = "1993",

doi = "10.1007/3-540-57273-2_61",

language = "English",

isbn = "978-3-540-57273-2",

volume = "726",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "260--271",

editor = "Thomas Lengauer",

booktitle = "Algorithms—ESA '93",

}

Kloks, T, Bodlaender, H, Müller, H & Kratsch, D 1993, Computing treewidth and minimum fill-in: All you need are the minimal separators. in T Lengauer (ed.), Algorithms—ESA '93: First Annual European Symposium Bad Honnef, Germany September 30–October 2, 1993 Proceedings. vol. 726, Lecture Notes in Computer Science, Springer, pp. 260-271. https://doi.org/10.1007/3-540-57273-2_61

Computing treewidth and minimum fill-in: All you need are the minimal separators. / Kloks, T.; Bodlaender, H.; Müller, H. et al.
Algorithms—ESA '93: First Annual European Symposium Bad Honnef, Germany September 30–October 2, 1993 Proceedings. ed. / Thomas Lengauer. Vol. 726 Springer, 1993. p. 260-271 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

TY - CHAP

T1 - Computing treewidth and minimum fill-in: All you need are the minimal separators

AU - Kloks, T.

AU - Bodlaender, H.

AU - Müller, H.

AU - Kratsch, D.

PY - 1993

Y1 - 1993

N2 - Consider a class of graphs G having a polynomial time algorithm computing the set of all minimal separators for every graph in G . We show that there is a polynomial time algorithm for treewidth and minimum fill-in, respectively, when restricted to the class G . Many interesting classes of intersection graphs have a polynomial time algorithm computing all minimal separators, like permutation graphs, circle graphs, circular arc graphs, distance hereditary graphs, chordal bipartite graphs etc. Our result generalizes earlier results for the treewidth and minimum fill-in for several of these classes. We also consider the related problems pathwidth and interval completion when restricted to some special graph classes.

AB - Consider a class of graphs G having a polynomial time algorithm computing the set of all minimal separators for every graph in G . We show that there is a polynomial time algorithm for treewidth and minimum fill-in, respectively, when restricted to the class G . Many interesting classes of intersection graphs have a polynomial time algorithm computing all minimal separators, like permutation graphs, circle graphs, circular arc graphs, distance hereditary graphs, chordal bipartite graphs etc. Our result generalizes earlier results for the treewidth and minimum fill-in for several of these classes. We also consider the related problems pathwidth and interval completion when restricted to some special graph classes.

U2 - 10.1007/3-540-57273-2_61

DO - 10.1007/3-540-57273-2_61

M3 - Chapter

SN - 978-3-540-57273-2

VL - 726

T3 - Lecture Notes in Computer Science

SP - 260

EP - 271

BT - Algorithms—ESA '93

A2 - Lengauer, Thomas

PB - Springer

ER -

Kloks T, Bodlaender H, Müller H, Kratsch D. Computing treewidth and minimum fill-in: All you need are the minimal separators. In Lengauer T, editor, Algorithms—ESA '93: First Annual European Symposium Bad Honnef, Germany September 30–October 2, 1993 Proceedings. Vol. 726. Springer. 1993. p. 260-271. (Lecture Notes in Computer Science). doi: 10.1007/3-540-57273-2_61

Computing treewidth and minimum fill-in: All you need are the minimal separators

Abstract

Publication series

Access to Document

Fingerprint

Cite this