Algorithmic approach to the satisfactory graph partitioning problem

DOI10.1016/S0377-2217(99)00459-2zbMATH Open0965.90053OpenAlexW2039311359MaRDI QIDQ1580976FDOQ1580976

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

Recommendations

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

zbMATH Keywords

graph partitiongraph theoryheuristic algorithms

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithms for the maximum satisfiability problem

Cited In (33)

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

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)