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

      0 references
      1989
      0 references
      tree width
      0 references
      path width
      0 references
      NP-complete
      0 references
      dominating set
      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

      Identifiers