Satisfactory graph partition, variants, and generalizations

DOI10.1016/J.EJOR.2009.10.019zbMATH Open1209.05237OpenAlexW2029754745MaRDI QIDQ976309FDOQ976309

Authors: Cristina Bazgan, Zsolt Tuza, 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

Recommendations

• The satisfactory partition problem
• Computing and Combinatorics
• Algorithms and Computation
• The balanced satisfactory partition problem
• scientific article; zbMATH DE number 1933255

zbMATH Keywords

combinatorial optimizationapproximation algorithmcomplexity theorydegree constraintsvertex partition

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (24)

• The satisfactory partition problem
• Stabilization Time in Weighted Minority Processes
• Internal partitions of regular graphs
• A 2-approximation for the maximum satisfying bisection problem
• The balanced satisfactory partition problem
• Algorithms and Computation
• Improper C-colorings of graphs
• Generalized graph \(k\)-coloring games
• Approximation of satisfactory bisection problems
• A branch-and-price-and-cut method for computing an optimal bramble
• (Dis)assortative partitions on random regular graphs
• Structural and algorithmic properties of 2-community structures
• Aspects of upper defensive alliances
• Computing and Combinatorics
• New insight into 2-community structures in graphs with applications in social networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• On non-trivial Nash stable partitions in additive hedonic games with symmetric 0/1-utilities
• On perfectly friendly bisections of random graphs
• The efficient partition surplus Owen graph value
• A heuristic approach for dividing graphs into bi-connected components with a size constraint
• Algorithmic approach to the satisfactory graph partitioning problem
• Asymptotically almost every \(2r\)-regular graph has an internal partition
• A note on internal partitions: the 5-regular case and beyond

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976309)