zbMATH — the first resource for mathematics

Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. (English) Zbl 0818.68118
Summary: 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 not 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 show that unless P = NP there are no absolute approximation algorithms for any of the parameters.

68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI