Satisfactory graph partition, variants, and generalizations

DOI10.1016/j.ejor.2009.10.019zbMath1209.05237MaRDI QIDQ976309

Zsolt Tuza, Cristina Bazgan, Daniel Vanderpooten

Publication date: 11 June 2010

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2009.10.019

zbMATH Keywords

combinatorial optimization; approximation algorithm; complexity theory; vertex partition; degree constraints

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

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

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

On non-trivial Nash stable partitions in additive hedonic games with symmetric 0/1-utilities, A 2-approximation for the maximum satisfying bisection problem, Improper C-colorings of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Acyclic colorings of graphs with bounded degree
• On a theorem about vertex colorings of graphs
• Unfriendly partitions of a graph
• On total functions, existence theorems and computational complexity
• Upper bounds on the bisection width of 3- and 4-regular graphs
• Efficient algorithms for decomposing graphs under degree constraints
• Approximation of satisfactory bisection problems
• On stable cutsets in claw-free graphs and planar graphs
• Matching cutsets in graphs of diameter 2
• Some complexity problems on single input double output controllers
• Graph decomposition with constraints in the minimum degree
• The isoperimetric number of random regular graphs
• Fast projection methods for minimal design problems in linear system theory
• Balanced graphs with minimum degree constraints
• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• Covering the vertex set of a graph with subgraphs of smaller degree
• Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality
• Graphical decompositions
• On stable cutsets in line graphs
• Algorithmic approach to the satisfactory graph partitioning problem
• Graph partitions with minimum degree constraints
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• Variable degeneracy: Extensions of Brooks' and Gallai's theorems
• Degree-constrained decompositions of graphs: Bounded treewidth and planarity
• The satisfactory partition problem
• Simple Local Search Problems that are Hard to Solve
• Recognizing decomposable graphs
• Graph decomposition with constraints on the connectivity and minimum degree
• Optimal Vertex Partitions
• Networks immune to isolated line failures
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Approximation algorithms for NP-complete problems on planar graphs
• ON DISJOINT CYCLES
• On the Edge-Expansion of Graphs
• A Split&Push Approach to 3D Orthogonal Drawing
• The bisection width of cubic graphs
• Algorithms and Computation
• Matching cutsets in graphs
• Paths, Trees, and Flowers
• Neural networks and physical systems with emergent collective computational abilities.
• ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
• Computing and Combinatorics
• Graph-Theoretic Concepts in Computer Science
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic