An exact combinatorial algorithm for minimum graph bisection
From MaRDI portal
Publication:747771
DOI10.1007/S10107-014-0811-ZzbMATH Open1327.90255OpenAlexW1978857010MaRDI QIDQ747771FDOQ747771
Authors: Daniel Delling, Daniel Fleischman, Andrew V. Goldberg, Ilya Razenshteyn, Renato F. Werneck 
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
Recommendations
- Exact combinatorial branch-and-bound for graph bisection
- scientific article; zbMATH DE number 5237020
- An efficient algorithm for graph bisection of triangularizations
- An exact algorithm for graph partitioning
- Graph Bipartization and via minimization
- scientific article; zbMATH DE number 1817784
- scientific article; zbMATH DE number 666305
- On the graph bisection problem
- Exact algorithms for the vertex separator problem in graphs
- On minimum bisection and related partition problems in graphs with bounded tree width
Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27)
Cites Work
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- Graph Partitioning and Graph Clustering
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- An Automatic Method of Solving Discrete Programming Problems
- Title not available (Why is that?)
- Applications of a Planar Separator Theorem
- Some simplified NP-complete graph problems
- A new approach to the maximum-flow problem
- A combined evolutionary search and multilevel optimisation approach to graph-partitioning
- An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
- Title not available (Why is that?)
- Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
- A new approach to the minimum cut problem
- Parallel Branch-and-Branch Algorithms: Survey and Synthesis
- A framework for solving VLSI graph layout problems
- The node capacitated graph partitioning problem: A computational study
- Min-cut clustering
- An exact algorithm for graph partitioning
- Title not available (Why is that?)
- Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
- Solving Graph Bisection Problems with Semidefinite Programming
- A faster approximation algorithm for the Steiner problem in graphs
- An \(\mathcal{O}(n^4)\) time algorithm to compute the bisection width of solid grid graphs
- Finding optimal solutions to the graph partitioning problem with heuristic search
- Contraction decomposition in \(h\)-minor-free graphs and algorithmic applications
- Integer Programming and Combinatorial Optimization
- Quadratic \(0/1\) optimization and a decomposition approach for the placement of electronic circuits
- Exact combinatorial branch-and-bound for graph bisection
- Minimum bisection is fixed parameter tractable
- Title not available (Why is that?)
- A branch-and-cut algorithm for the equicut problem
- An experimental evaluation of point-to-point shortest path calculation on road networks with precalculated edge-flags
- Title not available (Why is that?)
- SHARC, fast and robust unidirectional routing
- A PROBE-Based Heuristic for Graph Partitioning
- Maximum flows by incremental breadth-first search
- LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
- Multicommodity flow approximation used for exact graph partitioning
- A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem
- Better Bounds for Graph Bisection
- Distributed Evolutionary Graph Partitioning
- Engineering multilevel overlay graphs for shortest-path queries
- Title not available (Why is that?)
Cited In (13)
- Exact algorithms for the vertex separator problem in graphs
- Exact combinatorial branch-and-bound for graph bisection
- Continuum limit of total variation on point clouds
- An effective iterated tabu search for the maximum bisection problem
- Title not available (Why is that?)
- Hybrid genetic algorithm within branch-and-cut for the minimum graph bisection problem
- Title not available (Why is that?)
- Approximating the minimum bisection size (extended abstract)
- A bounded-error quantum polynomial-time algorithm for two graph bisection problems
- Minimum bisection is NP-hard on unit disk graphs
- An exact approach for the multi-constraint graph partitioning problem
- Graph bisection with Pareto optimization
- Optimal Cheeger cuts and bisections of random geometric graphs
Uses Software
This page was built for publication: An exact combinatorial algorithm for minimum graph bisection
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q747771)
