Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0818.68118
Bodlaender, Hans L.; Gilbert, John R.; Hafsteinsson, Hjálmtýr; Kloks, Ton
Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. (English)
[J] J. Algorithms 18, No.2, 238-255 (1995). ISSN 0196-6774

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\sp 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.

MSC 2000:: *68R10 Graph theory in connection with computer science

Keywords: sparse matrix factorization; vertex separators

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]