zbMATH — the first resource for mathematics

New upper bound heuristics for treewidth. (English) Zbl 1121.68355
Nikoletseas, Sotiris E. (ed.), Experimental and efficient algorithms. 4th international workshop, WEA 2005, Santorini Island, Greece, May 10–13, 2005. Proceedings. Berlin Springer (ISBN 3-540-25920-1/pbk). Lecture Notes in Computer Science 3503, 216-227 (2005).
Summary: In this paper, we introduce and evaluate some heuristics to find an upper bound on the treewidth of a given graph. Each of the heuristics selects the vertices of the graph one by one, building an elimination list. The heuristics differ in the criteria used for selecting vertices. These criteria depend on the fill-in of a vertex and the related new notion of the fill-in-excluding-one-neighbor. In several cases, the new heuristics improve the bounds obtained by existing heuristics.
For the entire collection see [Zbl 1073.68008].

68R10 Graph theory (including graph drawing) in computer science
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Full Text: DOI