Algorithmic approach to the satisfactory graph partitioning problem

DOI10.1016/S0377-2217(99)00459-2zbMath0965.90053OpenAlexW2039311359MaRDI QIDQ1580976

Michael U. Gerber, Daniel Kobler

Publication date: 23 November 2000

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0377-2217(99)00459-2

zbMATH Keywords

graph theoryheuristic algorithmsgraph partition

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Cites Work

• Algorithms for the maximum satisfiability problem
• Unnamed Item
• Unnamed Item

Related Items (31)

Algorithms for vertex-partitioning problems on graphs with fixed clique-width. ⋮ The balanced satisfactory partition problem ⋮ Degree-constrained decompositions of graphs: Bounded treewidth and planarity ⋮ Very cost effective bipartitions in graphs ⋮ ON LOCALLY-BALANCED 2-PARTITIONS OF BIPARTITE GRAPHS ⋮ LOCALLY-BALANCED $k$-PARTITIONS OF GRAPHS ⋮ Degree-constrained 2-partitions of graphs ⋮ Friendly bisections of random graphs ⋮ A strong formulation for the graph partition problem ⋮ Min-max communities in graphs: complexity and computational properties ⋮ Graph partitions under average degree constraint ⋮ Alliances in graphs: parameters, properties and applications -- a survey ⋮ Approximation of satisfactory bisection problems ⋮ SELF-STABILIZING ALGORITHMS FOR UNFRIENDLY PARTITIONS INTO TWO DISJOINT DOMINATING SETS ⋮ A branch-and-price-and-cut method for computing an optimal bramble ⋮ A 2-approximation for the maximum satisfying bisection problem ⋮ Satisfactory graph partition, variants, and generalizations ⋮ The satisfactory partition problem ⋮ Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications ⋮ Parameterized complexity of satisfactory partition problem ⋮ Finding \(k\)-community structures in special graph classes ⋮ On perfectly friendly bisections of random graphs ⋮ 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 ⋮ Bounds on cost effective domination numbers ⋮ Convergence and hardness of strategic Schelling segregation ⋮ A note on the satisfactory partition problem: constant size requirement ⋮ Offensive alliances in graphs ⋮ (Dis)assortative partitions on random regular graphs

This page was built for publication: Algorithmic approach to the satisfactory graph partitioning problem