Approximation algorithms for balancing signed graphs

DOI10.1007/978-3-030-57602-8_36zbMath1482.68172OpenAlexW3047927251MaRDI QIDQ2039689

Zhuo Diao, Zhongzheng Tang

Publication date: 5 July 2021

Full work available at URL: https://doi.org/10.1007/978-3-030-57602-8_36

zbMATH Keywords

signed graphapproximation algorithmsNP-hardnessbalance

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

Cites Work

• Unnamed Item
• Social balance on networks: the dynamics of friendship and enmity
• A mathematical bibliography of signed and gain graphs and allied areas
• On the notion of balance of a signed graph
• Gadgets, Approximation, and Linear Programming
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?

This page was built for publication: Approximation algorithms for balancing signed graphs