No label defined (Q4734768)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4121438
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4121438 |
Statements
1989
0 references
tree width
0 references
path width
0 references
NP-complete
0 references
dominating set
0 references
0.772805392742157
0 references
0.7703559994697571
0 references
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.
0 references