Satisfactory graph partition, variants, and generalizations

DOI10.1016/J.EJOR.2009.10.019MaRDI QIDQ976309zbMATHOpenAlexFDO

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

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)

Recommendations

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

Cites work

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

Cited in

(25)

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

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)