On the sum-max graph partitioning problem

DOI10.1016/j.tcs.2013.11.024zbMath1418.68108OpenAlexW1993617716MaRDI QIDQ2453173

Marin Bougeret, Rémi Watrigant, Rodolphe Giroudeau, Jean-Claude Konig

Publication date: 6 June 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.11.024

zbMATH Keywords

combinatorial optimizationapproximation algorithmgraph partitioning problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Cites Work

• A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
• Complexity of graph partition problems
• Algorithms for Partition of Some Class of Graphs under Compaction
• Sum-Max Graph Partitioning Problem
• Finding k Cuts within Twice the Optimal
• Computing and Combinatorics
• Computational Complexity of Compaction to Reflexive Cycles
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the sum-max graph partitioning problem