Deciding Clique-Width for Graphs of Bounded Tree-Width

DOI10.7155/JGAA.00065MaRDI QIDQ4435348zbMATH OpenOpenAlexFDO

Authors W. Espelage, Frank Gurski, Egon Wanke

Publication date 30 November 2003

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://eudml.org/doc/50437

zbMATH Keywords

linear time algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• scientific article; zbMATH DE number 1830724
• A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width
• scientific article; zbMATH DE number 1696534
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• 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 2044924
• On the Relationship Between Clique-Width and Treewidth
• Upper bounds to the clique width of graphs
• Approximating clique-width and branch-width

Cited in

(33)

• The NLC-width and clique-width for powers of graphs of bounded tree-width
• Graph operations characterizing rank-width
• Query efficient implementation of graphs of bounded clique-width
• Structure and algorithms for (cap, even hole)-free graphs
• Computing the clique-width of cactus graphs
• Constrained-path labellings on graphs of bounded clique-width
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Treewidth versus clique number in graph classes with a forbidden structure
• On quasi-planar graphs: clique-width and logical description
• Efficient computation of the oriented chromatic number of recursively defined digraphs
• Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width
• Polynomial algorithms for protein similarity search for restricted mRNA structures
• From tree-decompositions to clique-width terms
• Line graphs of bounded clique-width
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Approximating clique-width and branch-width
• Linear layouts measuring neighbourhoods in graphs
• Vertex disjoint paths on clique-width bounded graphs
• On the relationship between NLC-width and linear NLC-width
• Regular independent sets
• The relative clique-width of a graph
• Vertex cover meets scheduling
• Computing the clique-width of large path powers in linear time via a new characterisation of clique-width
• Polynomial-time recognition of clique-width 3 graphs
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• The behavior of clique-width under graph operations and graph transformations
• Inductive computations on graphs defined by clique-width expressions
• A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width
• Cluster editing on cographs and related classes
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• Directed NLC-width
• On a disparity between relative cliquewidth and relative NLC-width

This page was built for publication: Deciding Clique-Width for Graphs of Bounded Tree-Width

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