Bodlaender, Hans L.; Gilbert, John R.; Hafsteinsson, Hjálmtýr; Kloks, Ton Approximating treewidth, pathwidth, and minimum elimination tree height. (English) Zbl 0768.68121 Graph-theoretic concepts in computer science, Proc. 17th Int. Workshop, Fischbachau/Ger. 1991, Lect. Notes Comput. Sci. 570, 1-12 (1992). Summary: [For the entire collection see Zbl 0759.00014.]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. Cited in 15 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science 05C05 Trees 05C35 Extremal problems in graph theory 05C85 Graph algorithms (graph-theoretic aspects) Keywords:sparse matrix factorization; algorithm of Leighton; vertex separators; minimum front size; treewidth; pathwidth; minimum elimination tree height; approximation algorithms Citations:Zbl 0759.00014 PDFBibTeX XMLCite \textit{H. L. Bodlaender} et al., Lect. Notes Comput. Sci. 570, 1--12 (1992; Zbl 0768.68121)