TY - GEN
T1 - A natural generalization of bounded tree-width and bounded clique-width
AU - Fürer, Martin
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84899972051&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84899972051&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-54423-1_7
DO - 10.1007/978-3-642-54423-1_7
M3 - Conference contribution
AN - SCOPUS:84899972051
SN - 9783642544224
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 72
EP - 83
BT - LATIN 2014
PB - Springer Verlag
T2 - 11th Latin American Theoretical Informatics Symposium, LATIN 2014
Y2 - 31 March 2014 through 4 April 2014
ER -