TY - JOUR
T1 - Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
AU - Bodlaender, H. L.
AU - Gilbert, J. R.
AU - Hafsteinsson, H.
AU - Kloks, T.
PY - 1995/3/1
Y1 - 1995/3/1
N2 - 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(log2n) (pathwidth and minimum elimination tree height) times the optimal values. In addition, we show that unless P = NP there are no absolute approximation algorithms for any of the parameters.
AB - 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(log2n) (pathwidth and minimum elimination tree height) times the optimal values. In addition, we show that unless P = NP there are no absolute approximation algorithms for any of the parameters.
UR - http://www.scopus.com/inward/record.url?scp=0008799320&partnerID=8YFLogxK
U2 - 10.1006/jagm.1995.1009
DO - 10.1006/jagm.1995.1009
M3 - Article
AN - SCOPUS:0008799320
SN - 0196-6774
VL - 18
SP - 238
EP - 255
JO - Journal of Algorithms
JF - Journal of Algorithms
IS - 2
ER -