Satisfactory graph partition, variants, and generalizations
From MaRDI portal
Publication:976309
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
combinatorial optimization; approximation algorithm; complexity theory; vertex partition; degree constraints
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, Structural and algorithmic properties of 2-community structures, A branch-and-price-and-cut method for computing an optimal bramble, A heuristic approach for dividing graphs into bi-connected components with a size constraint, Internal Partitions of Regular Graphs, New Insight into 2-Community Structures in Graphs with Applications in Social Networks
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
