Approximating Treewidth, Pathwidth, and Minimum Elimination Tree Height. Bodlaender, H. L., Gilbert, J. R., Kloks, T., & Hafsteinsson, H. In Proc. of Graph-Theoretic Concepts in Computer Science (WG 1991), volume 570, of Lect Notes Comput Sci, pages 1–12, 1992.
doi  abstract   bibtex   
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^2 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.
@InProceedings{bodlaender92approximating,
  author    = {Hans L. Bodlaender and John R. Gilbert and Ton Kloks and Hj{\'a}lmtyr Hafsteinsson},
  title     = {Approximating Treewidth, Pathwidth, and Minimum Elimination Tree Height},
  booktitle = {Proc. of Graph-Theoretic Concepts in Computer Science (WG 1991)},
  year      = {1992},
  volume    = {570},
  series    = lncs,
  pages     = {1--12},
  publisher = Springer,
  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^2 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.},
  doi       = {10.1007/3-540-55121-2_1},
  keywords  = {treewidth; pathwidth; approximation},
  owner     = {Sebastian},
  timestamp = {2014.04.08},
}
Downloads: 0