An exact combinatorial algorithm for minimum graph bisection
From MaRDI portal
Publication:747771
DOI10.1007/S10107-014-0811-ZzbMath1327.90255OpenAlexW1978857010MaRDI QIDQ747771
Renato F. Werneck, Daniel Fleischman, Daniel Delling, Andrew V. Goldberg, Ilya Razenshteyn
Publication date: 19 October 2015
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1721.1/103396
Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (6)
An effective iterated tabu search for the maximum bisection problem ⋮ Optimal Cheeger cuts and bisections of random geometric graphs ⋮ Graph Bisection with Pareto Optimization ⋮ An exact approach for the multi-constraint graph partitioning problem ⋮ A bounded-error quantum polynomial-time algorithm for two graph bisection problems ⋮ Continuum limit of total variation on point clouds
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A framework for solving VLSI graph layout problems
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- Some simplified NP-complete graph problems
- The node capacitated graph partitioning problem: A computational study
- Min-cut clustering
- Quadratic \(0/1\) optimization and a decomposition approach for the placement of electronic circuits
- A branch-and-cut algorithm for the equicut problem
- A combined evolutionary search and multilevel optimisation approach to graph-partitioning
- An exact algorithm for graph partitioning
- LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
- Finding optimal solutions to the graph partitioning problem with heuristic search
- Better Bounds for Graph Bisection
- An $\mathcal{O}(n^4)$ Time Algorithm to Compute the Bisection Width of Solid Grid Graphs
- Maximum Flows by Incremental Breadth-First Search
- An Automatic Method of Solving Discrete Programming Problems
- Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
- A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem
- A new approach to the maximum-flow problem
- Applications of a Planar Separator Theorem
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- A new approach to the minimum cut problem
- Solving Graph Bisection Problems with Semidefinite Programming
- A PROBE-Based Heuristic for Graph Partitioning
- An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
- Parallel Branch-and-Branch Algorithms: Survey and Synthesis
- Graph Partitioning and Graph Clustering
- Distributed Evolutionary Graph Partitioning
- Exact Combinatorial Branch-and-Bound for Graph Bisection
- Minimum bisection is fixed parameter tractable
- Engineering multilevel overlay graphs for shortest-path queries
- SHARC
- Contraction decomposition in h-minor-free graphs and algorithmic applications
- Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
- Integer Programming and Combinatorial Optimization
- Algorithms - ESA 2003
- A faster approximation algorithm for the Steiner problem in graphs
This page was built for publication: An exact combinatorial algorithm for minimum graph bisection
