Satisfactory graph partition, variants, and generalizations
From MaRDI portal
Publication:976309
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
combinatorial optimizationapproximation algorithmcomplexity theoryvertex partitiondegree constraints
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
