Algorithms for vertex-partitioning problems on graphs with fixed clique-width.

DOI10.1016/S0304-3975(02)00725-9zbMath1042.68092MaRDI QIDQ1874418

Michael U. Gerber, Daniel Kobler

Publication date: 25 May 2003

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

zbMATH Keywords

Polynomial algorithmsGraph partitioningClique-width

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (30)

Star colouring of bounded degree graphs and regular graphs ⋮ The balanced satisfactory partition problem ⋮ Degree-constrained decompositions of graphs: Bounded treewidth and planarity ⋮ MSOL partitioning problems on graphs of bounded treewidth and clique-width ⋮ Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems ⋮ Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ Clique‐width: Harnessing the power of atoms ⋮ Graph classes with and without powers of bounded clique-width ⋮ Graphs of separability at most 2 ⋮ Polynomial-time recognition of clique-width \(\leq 3\) graphs ⋮ Min-max communities in graphs: complexity and computational properties ⋮ Directed NLC-width ⋮ Latency-bounded target set selection in social networks ⋮ Graphs of Separability at Most Two: Structural Characterizations and Their Consequences ⋮ A branch-and-price-and-cut method for computing an optimal bramble ⋮ \(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 ⋮ Satisfactory graph partition, variants, and generalizations ⋮ The satisfactory partition problem ⋮ Unnamed Item ⋮ On the Boolean-Width of a Graph: Structure and Applications ⋮ Cluster deletion on interval graphs and split related graphs ⋮ Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications ⋮ Parameterized complexity of satisfactory partition problem ⋮ Asymptotically almost every \(2r\)-regular graph has an internal partition ⋮ Unnamed Item ⋮ A note on the satisfactory partition problem: constant size requirement ⋮ Offensive alliances in graphs ⋮ Edge dominating set and colorings on graphs with fixed clique-width ⋮ Tree Pivot-Minors and Linear Rank-Width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Monadic second-order evaluations on tree-decomposable graphs
• A partial k-arboretum of graphs with bounded treewidth
• Splitting trees
• Algorithmic aspects of majority domination
• Algorithmic approach to the satisfactory graph partitioning problem
• Majority domination in graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Easy problems for tree-decomposable graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Graph colorings with local constraints -- a survey
• An algebraic theory of graph reduction
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Fixed-Parameter Tractability and Completeness I: Basic Results
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic

This page was built for publication: Algorithms for vertex-partitioning problems on graphs with fixed clique-width.