Die Baumweite von Graphen als ein Maß für die Kompliziertheit algorithmischer Probleme. (German) Zbl 0684.68061

Scheffler, Petra

Rep., Akad. Wiss. DDR, Karl-Weierstraß-Inst. Math. 04/89, 106 p. (1989).

Eine Baumzerlegung für einen ungerichteten Graphen \(G=(V,E)\) ist ein Paar (T,\(\underset {=} X)\) bestehend aus einem ungerichteten Baum \(T=(VT,ET)\) und einer Mengenfamilie \(\underset {=} X=\{X_ t\subseteq V:\) \(t\in VT\}\) mit
(1) \(\cup_{t\in VT}X_ t=V,\)
(2) \(\forall \{u,v\}\in E:\) \(\exists t\in VT:\) \(\{\) u,v\(\}\) \(\subseteq X,\)
(3) liegt \(t'\) zwischen t und \(t''\) in T, so gilt \(X_ t\cap X_{t''}\subseteq X_{t'}.\)
Die Weite der Zerlegung ist gleich \(\max_{t\in VT}(| X_ t| - 1)\). Die Baumweite eines Graphen ist die minimale Weite einer zugehörigen Zerlegung. Serienparallele Graphen, Halingraphen oder außenplanare Graphen haben eine geringe Baumweite.
Das Problem, ob ein Graph eine Baumweite von höchstens w besitzt, ist (incl. die Bestimmung einer zugehörigen Zerlegung) mit \(O(n^{w+2})\) Zeit- und Spreicheraufwand lösbar. Die Wegbreite von Bäumen ist in O(n log n) Schritten bestimmbar.
Für ca. 50 bekannte NP-vollständige Probleme wird aufgrund der Tatsache, daß diese sich über die Existenz von Teilen des Graphen definieren lassen, die eine Konjunktion lokal verifizierbarer (bzw. auf Cliquen verifizierbarer) Eigenschaften erfüllen lassen, gezeigt, daß sie für Graphen beschränkter Baumweite in Linearzeit lösbar sind.
Für die Entscheidung, ob es in G m dominierende Mengen gibt, und für die Bestimmung disjunkter Wege wird eine solche Lösung entwickelt.
Verwandte Betrachtungen werden für die Wegbreite von Graphen angestellt.

Reviewer: J.Ebert

MSC:

68Q25	Analysis of algorithms and problem complexity
68R10	Graph theory (including graph drawing) in computer science

Keywords:

tree width; path width; NP-complete; dominating set