A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width

DOI10.1007/978-3-642-54423-1_7MaRDI QIDQ5405029zbMATH OpenOpenAlexFDO

Authors Martin Fürer

Publication date 31 March 2014

Published in LATIN 2014: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.1810

zbMATH Keywords

clique-widthtree-widthFPTXPfusion-width

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: 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.

Recommendations

• scientific article; zbMATH DE number 1830724
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• scientific article; zbMATH DE number 1696534
• On the OBDD Size for Graphs of Bounded Tree- and Clique-Width
• On the OBDD size for graphs of bounded tree- and clique-width
• scientific article; zbMATH DE number 932194
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• A managed Bayesian risk approach for decision making alternatives
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• scientific article; zbMATH DE number 4121424

Cited in

(10)

• On the expressive power of CNF formulas of bounded tree- and clique-width
• Graph classes and the switch Markov chain for matchings
• Spined categories: generalizing tree-width beyond graphs
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• Maximum matching in almost linear time on graphs of bounded clique-width
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Multi-clique-width
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• Optimal centrality computations within bounded clique-width graphs

This page was built for publication: A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5405029)