Algorithmic approach to the satisfactory graph partitioning problem

DOI10.1016/S0377-2217(99)00459-2MaRDI QIDQ1580976zbMATH OpenOpenAlexFDO

Authors 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 partitiongraph theoryheuristic algorithms

Mathematics Subject Classification ID

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

Recommendations

• The satisfactory partition problem
• Satisfactory graph partition, variants, and generalizations
• Computing and Combinatorics
• Algorithms and Computation
• scientific article; zbMATH DE number 2104729

Cites work

• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 67483 (Why is no real title available?)
• Algorithms for the maximum satisfiability problem

Cited in

(33)

• A note on the satisfactory partition problem: constant size requirement
• Alliances and Related Domination Parameters
• Approximation of satisfactory bisection problems
• Parameterized complexity of satisfactory partition problem
• A strong formulation for the graph partition problem
• The balanced satisfactory partition problem
• Convergence and hardness of strategic Schelling segregation
• Bounds on cost effective domination numbers
• Degree-constrained 2-partitions of graphs
• Degree-constrained decompositions of graphs: Bounded treewidth and planarity
• Asymptotically almost every \(2r\)-regular graph has an internal partition
• (Dis)assortative partitions on random regular graphs
• The satisfactory partition problem
• Friendly bisections of random graphs
• Stabilization Time in Weighted Minority Processes
• Offensive alliances in graphs
• Self-stabilizing algorithms for unfriendly partitions into two disjoint dominating sets
• Min-max communities in graphs: complexity and computational properties
• LOCALLY-BALANCED $k$-PARTITIONS OF GRAPHS
• Satisfactory graph partition, variants, and generalizations
• Alliances in graphs: parameters, properties and applications -- a survey
• Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications
• Very cost effective bipartitions in graphs
• scientific article; zbMATH DE number 4076980 (Why is no real title available?)
• scientific article; zbMATH DE number 1933255 (Why is no real title available?)
• A 2-approximation for the maximum satisfying bisection problem
• Finding \(k\)-community structures in special graph classes
• On perfectly friendly bisections of random graphs
• A branch-and-price-and-cut method for computing an optimal bramble
• On locally-balanced 2-partitions of bipartite graphs
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• Internal partitions of regular graphs
• Graph partitions under average degree constraint

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

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