Exact Combinatorial Branch-and-Bound for Graph Bisection

DOI10.1137/1.9781611972924.3zbMath1430.68192OpenAlexW131283763MaRDI QIDQ5233715

Ilya Razenshteyn, Andrew V. Goldberg, Renato F. Werneck, Daniel Delling

Publication date: 12 September 2019

Published in: 2012 Proceedings of the Fourteenth Workshop on Algorithm Engineering and Experiments (ALENEX) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611972924.3

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (10)

Minimum bisection is NP-hard on unit disk graphs ⋮ Graph Bisection with Pareto Optimization ⋮ ILP-Based Local Search for Graph Partitioning ⋮ On the parameterized complexity of computing balanced partitions in graphs ⋮ Distributed balanced partitioning via linear embedding ⋮ An exact combinatorial algorithm for minimum graph bisection ⋮ From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial) ⋮ Candidate Sets for Alternative Routes in Road Networks ⋮ Unnamed Item ⋮ Customizable Contraction Hierarchies

This page was built for publication: Exact Combinatorial Branch-and-Bound for Graph Bisection