MSOL partitioning problems on graphs of bounded treewidth and clique-width

DOI10.1016/j.tcs.2007.03.043zbMath1118.68107OpenAlexW2008361472MaRDI QIDQ884481

Michaël Rao

Publication date: 6 June 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.03.043

zbMATH Keywords

monadic second-order logictreewidthgraph algorithmsclique-widthvertex partitioning

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Automata and formal grammars in connection with logical questions (03D05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (45)

Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs ⋮ On coloring a class of claw-free graphs. ⋮ Clique cycle-transversals in distance-hereditary graphs ⋮ On the structure of graphs without claw, \(4K_1\) and co-R ⋮ Vertex coloring of graphs with few obstructions ⋮ Vertex partitioning problems on graphs with bounded tree width ⋮ On some domination colorings of graphs ⋮ Colouring diamond-free graphs ⋮ Characterizations of \((4 K_1,C_4,C_5)\)-free graphs ⋮ Colouring square-free graphs without long induced paths. ⋮ Bounding the Clique-Width of H-free Chordal Graphs ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ A coloring algorithm for \(4 K_1\)-free line graphs ⋮ Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ On the structure and clique‐width of (4K1,C4,C6,C7)‐free graphs ⋮ Clique‐width: Harnessing the power of atoms ⋮ Coloring \((4K_1,C_4,C_6)\)-free graphs ⋮ Bounding clique-width via perfect graphs ⋮ Clique-Width for Graph Classes Closed under Complementation ⋮ Directed NLC-width ⋮ Classifying the clique-width of \(H\)-free bipartite graphs ⋮ Automata for the verification of monadic second-order graph properties ⋮ Graphs vertex-partitionable into strong cliques ⋮ Polynomial cases for the vertex coloring problem ⋮ \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth ⋮ On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width ⋮ Parameterized shifted combinatorial optimization ⋮ Well-quasi-ordering versus clique-width: new results on bigenic classes ⋮ Clique-width and well-quasi-ordering of triangle-free graph classes ⋮ Partitioning graphs into induced subgraphs ⋮ Bounding Clique-Width via Perfect Graphs ⋮ Computations by fly-automata beyond monadic second-order logic ⋮ On the complexity of finding large odd induced subgraphs and odd colorings ⋮ Bounds and fixed-parameter algorithms for weighted improper coloring ⋮ Nontrivial path covers of graphs: existence, minimization and maximization ⋮ Unnamed Item ⋮ The intersection of two vertex coloring problems ⋮ Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes ⋮ Square-Free Graphs with No Six-Vertex Induced Path ⋮ Colouring vertices of triangle-free graphs without forests ⋮ Colouring square-free graphs without long induced paths ⋮ On coloring a class of claw-free and hole-twin-free graphs ⋮ Revising Johnson's table for the 21st century ⋮ More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints ⋮ Tree Pivot-Minors and Linear Rank-Width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithmic uses of the Feferman-Vaught theorem
• The strong perfect graph theorem
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• The monadic theory of order
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• Achromatic number is NP-complete for cographs and interval graphs
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• Linear time solvable optimization problems on graphs of bounded clique-width
• Handle-rewriting hypergraph grammars
• Approximating clique-width and branch-width
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• The first order properties of products of algebraic systems
• Easy problems for tree-decomposable graphs
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• On the Relationship Between Clique-Width and Treewidth
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: MSOL partitioning problems on graphs of bounded treewidth and clique-width