Approximating treewidth, pathwidth, and minimum elimination tree height

Hans L. Bodlaender; John R. Gilbert; Hjálmtýr Hafsteinsson; Ton Kloks

doi:10.1007/3-540-55121-2_1

Approximating treewidth, pathwidth, and minimum elimination tree height

Hans L. Bodlaender, John R. Gilbert, Hjálmtýr Hafsteinsson, Ton Kloks

Faculty of Industrial Engineering, Mechanical Engineering and Computer Science

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

28 Citations (Scopus)

Abstract

We show how the value of various parameters of graphs connected to sparse matrix factorization and other applications can be approximated using an algorithm of Leighton et al. that finds vertex separators of graphs. The approximate values of the parameters, which include minimum front size, treewidth, pathwidth, and minimum elimination tree height, are no more than O(log n) (minimum front size and treewidth) and O(log² n) (pathwidth and minimum elimination tree height) times the optimal values. In addition we examine the existence of bounded approximation algorithms for the parameters, and show that unless P = NP, there are no absolute approximation algorithms for them.

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science - 17th International Workshop, WG 1991, Proceedings
Editors	Gunther Schmidt, Rudolf Berghammer
Publisher	Springer Verlag
Pages	1-12
Number of pages	12
ISBN (Print)	9783540551218
DOIs	https://doi.org/10.1007/3-540-55121-2_1
Publication status	Published - 1992
Event	17th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1991 - Fischbachau, Germany Duration: 17 Jun 1991 → 19 Jun 1991

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	570 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	17th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1991
Country/Territory	Germany
City	Fischbachau
Period	17/06/91 → 19/06/91

Bibliographical note

Funding Information:
The notion of treewidth has several other applications (see e.g. \[Am85\]).I t is closely related to the pathwidth, which has among others important applications in the theory of VLSI layout. The pathwidth is equivalent to several other parameters of graphs, including the minimum chromatic number of an interval graph containing the graph as a subgraph and the node search number of a *Department of Computer Science, Utrecht University,P .O. Box 80.089, 3508 TB Utrecht, The Netherlands. The research of this author is partially supported by the ESPRIT II Basic Research Actions of the EC under Contract No. 3075 (project ALCOM). ?Xerox Palo Alto Research Center, 3333 Coyote Hill Road, Palo Alto, California 94304 USA, and Universityo f Bergen, Norway. ?Department of Computer Science, Universityo f Iceland, 101 Reykjav(k, Iceland. Department of Computer Science, Utrecht University.T he research of this author is supported by the Foundation for Computer Science (S.I.O.N.) of the Netherlands Organization for Scientific Research (N.W.O.) and by the ESPRIT II Basic Research Actions of the EC under Contract No. 3075 (project ALCOM).

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1992.

Access to Document

10.1007/3-540-55121-2_1

Cite this

Bodlaender, H. L., Gilbert, J. R., Hafsteinsson, H., & Kloks, T. (1992). Approximating treewidth, pathwidth, and minimum elimination tree height. In G. Schmidt, & R. Berghammer (Eds.), Graph-Theoretic Concepts in Computer Science - 17th International Workshop, WG 1991, Proceedings (pp. 1-12). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 570 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-55121-2_1

Bodlaender, Hans L. ; Gilbert, John R. ; Hafsteinsson, Hjálmtýr et al. / Approximating treewidth, pathwidth, and minimum elimination tree height. Graph-Theoretic Concepts in Computer Science - 17th International Workshop, WG 1991, Proceedings. editor / Gunther Schmidt ; Rudolf Berghammer. Springer Verlag, 1992. pp. 1-12 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{eef187d7faa245a4a524674ef9cf0260,

title = "Approximating treewidth, pathwidth, and minimum elimination tree height",

abstract = "We show how the value of various parameters of graphs connected to sparse matrix factorization and other applications can be approximated using an algorithm of Leighton et al. that finds vertex separators of graphs. The approximate values of the parameters, which include minimum front size, treewidth, pathwidth, and minimum elimination tree height, are no more than O(log n) (minimum front size and treewidth) and O(log2 n) (pathwidth and minimum elimination tree height) times the optimal values. In addition we examine the existence of bounded approximation algorithms for the parameters, and show that unless P = NP, there are no absolute approximation algorithms for them.",

author = "Bodlaender, {Hans L.} and Gilbert, {John R.} and Hj{\'a}lmt{\'y}r Hafsteinsson and Ton Kloks",

note = "Funding Information: The notion of treewidth has several other applications (see e.g. \[Am85\]).I t is closely related to the pathwidth, which has among others important applications in the theory of VLSI layout. The pathwidth is equivalent to several other parameters of graphs, including the minimum chromatic number of an interval graph containing the graph as a subgraph and the node search number of a *Department of Computer Science, Utrecht University,P .O. Box 80.089, 3508 TB Utrecht, The Netherlands. The research of this author is partially supported by the ESPRIT II Basic Research Actions of the EC under Contract No. 3075 (project ALCOM). ?Xerox Palo Alto Research Center, 3333 Coyote Hill Road, Palo Alto, California 94304 USA, and Universityo f Bergen, Norway. ?Department of Computer Science, Universityo f Iceland, 101 Reykjav(k, Iceland. Department of Computer Science, Utrecht University.T he research of this author is supported by the Foundation for Computer Science (S.I.O.N.) of the Netherlands Organization for Scientific Research (N.W.O.) and by the ESPRIT II Basic Research Actions of the EC under Contract No. 3075 (project ALCOM). Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1992.; 17th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1991 ; Conference date: 17-06-1991 Through 19-06-1991",

year = "1992",

doi = "10.1007/3-540-55121-2_1",

language = "English",

isbn = "9783540551218",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "1--12",

editor = "Gunther Schmidt and Rudolf Berghammer",

booktitle = "Graph-Theoretic Concepts in Computer Science - 17th International Workshop, WG 1991, Proceedings",

address = "Germany",

}

Bodlaender, HL, Gilbert, JR, Hafsteinsson, H & Kloks, T 1992, Approximating treewidth, pathwidth, and minimum elimination tree height. in G Schmidt & R Berghammer (eds), Graph-Theoretic Concepts in Computer Science - 17th International Workshop, WG 1991, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 570 LNCS, Springer Verlag, pp. 1-12, 17th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1991, Fischbachau, Germany, 17/06/91. https://doi.org/10.1007/3-540-55121-2_1

Approximating treewidth, pathwidth, and minimum elimination tree height. / Bodlaender, Hans L.; Gilbert, John R.; Hafsteinsson, Hjálmtýr et al.
Graph-Theoretic Concepts in Computer Science - 17th International Workshop, WG 1991, Proceedings. ed. / Gunther Schmidt; Rudolf Berghammer. Springer Verlag, 1992. p. 1-12 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 570 LNCS).

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

TY - GEN

T1 - Approximating treewidth, pathwidth, and minimum elimination tree height

AU - Bodlaender, Hans L.

AU - Gilbert, John R.

AU - Hafsteinsson, Hjálmtýr

AU - Kloks, Ton

N1 - Funding Information: The notion of treewidth has several other applications (see e.g. \[Am85\]).I t is closely related to the pathwidth, which has among others important applications in the theory of VLSI layout. The pathwidth is equivalent to several other parameters of graphs, including the minimum chromatic number of an interval graph containing the graph as a subgraph and the node search number of a *Department of Computer Science, Utrecht University,P .O. Box 80.089, 3508 TB Utrecht, The Netherlands. The research of this author is partially supported by the ESPRIT II Basic Research Actions of the EC under Contract No. 3075 (project ALCOM). ?Xerox Palo Alto Research Center, 3333 Coyote Hill Road, Palo Alto, California 94304 USA, and Universityo f Bergen, Norway. ?Department of Computer Science, Universityo f Iceland, 101 Reykjav(k, Iceland. Department of Computer Science, Utrecht University.T he research of this author is supported by the Foundation for Computer Science (S.I.O.N.) of the Netherlands Organization for Scientific Research (N.W.O.) and by the ESPRIT II Basic Research Actions of the EC under Contract No. 3075 (project ALCOM). Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1992.

PY - 1992

Y1 - 1992

N2 - We show how the value of various parameters of graphs connected to sparse matrix factorization and other applications can be approximated using an algorithm of Leighton et al. that finds vertex separators of graphs. The approximate values of the parameters, which include minimum front size, treewidth, pathwidth, and minimum elimination tree height, are no more than O(log n) (minimum front size and treewidth) and O(log2 n) (pathwidth and minimum elimination tree height) times the optimal values. In addition we examine the existence of bounded approximation algorithms for the parameters, and show that unless P = NP, there are no absolute approximation algorithms for them.

AB - We show how the value of various parameters of graphs connected to sparse matrix factorization and other applications can be approximated using an algorithm of Leighton et al. that finds vertex separators of graphs. The approximate values of the parameters, which include minimum front size, treewidth, pathwidth, and minimum elimination tree height, are no more than O(log n) (minimum front size and treewidth) and O(log2 n) (pathwidth and minimum elimination tree height) times the optimal values. In addition we examine the existence of bounded approximation algorithms for the parameters, and show that unless P = NP, there are no absolute approximation algorithms for them.

UR - http://www.scopus.com/inward/record.url?scp=85014532151&partnerID=8YFLogxK

U2 - 10.1007/3-540-55121-2_1

DO - 10.1007/3-540-55121-2_1

M3 - Conference contribution

AN - SCOPUS:85014532151

SN - 9783540551218

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 12

BT - Graph-Theoretic Concepts in Computer Science - 17th International Workshop, WG 1991, Proceedings

A2 - Schmidt, Gunther

A2 - Berghammer, Rudolf

PB - Springer Verlag

T2 - 17th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1991

Y2 - 17 June 1991 through 19 June 1991

ER -

Bodlaender HL, Gilbert JR, Hafsteinsson H, Kloks T. Approximating treewidth, pathwidth, and minimum elimination tree height. In Schmidt G, Berghammer R, editors, Graph-Theoretic Concepts in Computer Science - 17th International Workshop, WG 1991, Proceedings. Springer Verlag. 1992. p. 1-12. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-55121-2_1

Approximating treewidth, pathwidth, and minimum elimination tree height

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Fingerprint

Cite this