Approximation of satisfactory bisection problems

DOI10.1016/J.JCSS.2007.12.001MaRDI QIDQ931729zbMATH OpenOpenAlexFDO

Authors Cristina Bazgan, Zsolt Tuza, Daniel Vanderpooten

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

graphcomplexityapproximation algorithmNP-completenessdegree constraintsvertex partition

Mathematics Subject Classification ID

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

Recommendations

• A 2-approximation for the maximum satisfying bisection problem
• Computing and Combinatorics
• The satisfactory partition problem
• Satisfactory graph partition, variants, and generalizations
• Algorithmic approach to the satisfactory graph partitioning problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3220175 (Why is no real title available?)
• Algorithmic approach to the satisfactory graph partitioning problem
• Balanced graphs with minimum degree constraints
• Graph decomposition with constraints in the minimum degree
• Graph decomposition with constraints on the connectivity and minimum degree
• Graph partitions with minimum degree constraints
• Graphical decompositions
• Paths, Trees, and Flowers
• The hardness of approximation: Gap location
• The satisfactory partition problem

Cited in

(11)

• Structural and algorithmic properties of 2-community structures
• A polylogarithmic approximation of the minimum bisection
• Computing and Combinatorics
• Bisections above Tight Lower Bounds
• Complexity of the bisection method
• The most vital nodes with respect to independent set and vertex cover
• Satisfactory graph partition, variants, and generalizations
• New insight into 2-community structures in graphs with applications in social networks
• Average-Case Optimality of a Hybrid Secant-Bisection Method
• Lepp-bisection algorithms, applications and mathematical properties
• A 2-approximation for the maximum satisfying bisection problem

This page was built for publication: Approximation of satisfactory bisection problems

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