Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width
Ist Teil von
LATIN 2014: Theoretical Informatics, p.72-83
Ort / Verlag
Berlin, Heidelberg: Springer Berlin Heidelberg
Link zum Volltext
Quelle
Alma/SFX Local Collection
Beschreibungen/Notizen
We investigate a new width parameter, the fusion-width of a graph. It is a natural generalization of the tree-width, yet strong enough that not only graphs of bounded tree-width, but also graphs of bounded clique-width, trivially have bounded fusion-width. In particular, there is no exponential growth between tree-width and fusion-width, as is the case between tree-width and clique-width. The new parameter gives a good intuition about the relationship between tree-width and clique-width.