Satisfactory graph partition, variants, and generalizations

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

Zsolt Tuza, Daniel Vanderpooten, Cristina Bazgan

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 optimizationapproximation algorithmcomplexity theoryvertex partitiondegree constraints

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (14)

Structural and algorithmic properties of 2-community structures ⋮ New Insight into 2-Community Structures in Graphs with Applications in Social Networks ⋮ A heuristic approach for dividing graphs into bi-connected components with a size constraint ⋮ A note on internal partitions: the 5-regular case and beyond ⋮ Improper C-colorings of graphs ⋮ On non-trivial Nash stable partitions in additive hedonic games with symmetric 0/1-utilities ⋮ A branch-and-price-and-cut method for computing an optimal bramble ⋮ A 2-approximation for the maximum satisfying bisection problem ⋮ Aspects of upper defensive alliances ⋮ Generalized graph \(k\)-coloring games ⋮ Asymptotically almost every \(2r\)-regular graph has an internal partition ⋮ Internal Partitions of Regular Graphs ⋮ Stabilization Time in Weighted Minority Processes ⋮ (Dis)assortative partitions on random regular 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
• 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
• On decomposition of triangle-free graphs under degree constraints
• A Split&Push Approach to 3D Orthogonal Drawing
• The bisection width of cubic graphs
• Decomposing graphs with girth at least five under degree constraints
• 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

This page was built for publication: Satisfactory graph partition, variants, and generalizations