Deciding clique-width for graphs of bounded tree-width (extended abstract)

DOI10.1007/3-540-44634-6_9MaRDI QIDQ4778545zbMATH OpenFDO

Authors W. Espelage, Frank Gurski, Egon Wanke

Publication date 18 November 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2125/21250087

Mathematics Subject Classification ID

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

Cited in

(14)

• The NLC-width and clique-width for powers of graphs of bounded tree-width
• Query efficient implementation of graphs of bounded clique-width
• Computing the clique-width of cactus graphs
• Constrained-path labellings on graphs of bounded clique-width
• Treewidth versus clique number in graph classes with a forbidden structure
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Approximating clique-width and branch-width
• The relative clique-width of a graph
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• Inductive computations on graphs defined by clique-width expressions
• A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width
• On the expressive power of CNF formulas of bounded tree- and clique-width
• Acyclic coloring parameterized by directed clique-width

This page was built for publication: Deciding clique-width for graphs of bounded tree-width (extended abstract)

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