Deciding Clique-Width for Graphs of Bounded Tree-Width

DOI10.7155/JGAA.00065zbMATH Open1027.05093OpenAlexW2112067601MaRDI QIDQ4435348FDOQ4435348

Frank Gurski, Egon Wanke, W. Espelage

Publication date: 30 November 2003

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

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)

Cited In (32)

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

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Upper bounds to the clique width of graphs 👍 👎
• Approximating clique-width and branch-width 👍 👎
• On the Relationship Between Clique-Width and Treewidth 👍 👎
• On the OBDD size for graphs of bounded tree- and clique-width 👍 👎
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree 👍 👎
• A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width 👍 👎
• On the OBDD Size for Graphs of Bounded Tree- and Clique-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)