Approximation of satisfactory bisection problems

DOI10.1016/j.jcss.2007.12.001zbMath1140.68050OpenAlexW2023844733MaRDI QIDQ931729

Daniel Vanderpooten, Cristina Bazgan, Zsolt Tuza

Publication date: 26 June 2008

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2007.12.001

zbMATH Keywords

complexitygraphapproximation algorithmNP-completenessvertex partitiondegree constraints

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items

Structural and algorithmic properties of 2-community structures ⋮ New Insight into 2-Community Structures in Graphs with Applications in Social Networks ⋮ The most vital nodes with respect to independent set and vertex cover ⋮ A 2-approximation for the maximum satisfying bisection problem ⋮ Satisfactory graph partition, variants, and generalizations

Cites Work

• Unnamed Item
• Unnamed Item
• Graph decomposition with constraints in the minimum degree
• Balanced graphs with minimum degree constraints
• Graphical decompositions
• The hardness of approximation: Gap location
• Algorithmic approach to the satisfactory graph partitioning problem
• Graph partitions with minimum degree constraints
• The satisfactory partition problem
• Graph decomposition with constraints on the connectivity and minimum degree
• Paths, Trees, and Flowers