The satisfactory partition problem

DOI10.1016/j.dam.2005.10.014zbMath1095.68073OpenAlexW1982865350MaRDI QIDQ2495904

Zsolt Tuza, Cristina Bazgan, Daniel Vanderpooten

Publication date: 30 June 2006

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2005.10.014

zbMATH Keywords

complexitygraphpolynomial algorithmsatisfactory partition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (25)

The balanced satisfactory partition problem ⋮ Structural and algorithmic properties of 2-community structures ⋮ Very cost effective bipartitions in graphs ⋮ New Insight into 2-Community Structures in Graphs with Applications in Social Networks ⋮ Efficient algorithms for decomposing graphs under degree constraints ⋮ ON LOCALLY-BALANCED 2-PARTITIONS OF BIPARTITE GRAPHS ⋮ LOCALLY-BALANCED $k$-PARTITIONS OF GRAPHS ⋮ Degree-constrained 2-partitions of graphs ⋮ Min-max communities in graphs: complexity and computational properties ⋮ On non-trivial Nash stable partitions in additive hedonic games with symmetric 0/1-utilities ⋮ Approximation of satisfactory bisection problems ⋮ SELF-STABILIZING ALGORITHMS FOR UNFRIENDLY PARTITIONS INTO TWO DISJOINT DOMINATING SETS ⋮ A 2-approximation for the maximum satisfying bisection problem ⋮ Satisfactory graph partition, variants, and generalizations ⋮ Graphs without a partition into two proportionally dense subgraphs ⋮ Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications ⋮ Parameterized complexity of satisfactory partition problem ⋮ Alliances and Related Domination Parameters ⋮ Asymptotically almost every \(2r\)-regular graph has an internal partition ⋮ Internal Partitions of Regular Graphs ⋮ Stabilization Time in Weighted Minority Processes ⋮ Partitioning a graph into alliance free sets ⋮ Bounds on cost effective domination numbers ⋮ Convergence and hardness of strategic Schelling segregation ⋮ A note on the satisfactory partition problem: constant size requirement

Uses Software

• PARTITION

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithmic approach to the satisfactory graph partitioning problem
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• The NP-Completeness of Edge-Coloring
• ON DISJOINT CYCLES
• NP completeness of finding the chromatic index of regular graphs
• Algorithms and Computation

This page was built for publication: The satisfactory partition problem