Graph bisection with Pareto optimization

DOI10.1145/3173045MaRDI QIDQ4577953zbMATH OpenOpenAlexFDO

Authors Michael Hamann, Ben Strasser

Publication date 6 August 2018

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.03812

zbMATH Keywords

flowgraph bisectiongraph clusteringgraph partitioningshortest path

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Abstract: We introduce FlowCutter, a novel algorithm to compute a set of edge cuts or node separators that optimize cut size and balance in the Pareto-sense. Our core algorithm solves the balanced connected st-edge-cut problem, where two given nodes s and t must be separated by removing edges to obtain two connected parts. Using the core algorithm we build variants that compute node separators and are independent of s and t. Using the Pareto-set we can identify cuts with a particularly good trade-off between cut size and balance that can be used to compute contraction and minimum fill-in orders, which can be used in Customizable Contraction Hierarchies (CCH), a speed-up technique for shortest path computations. Our core algorithm runs in O(cm) time where m is the number of edges and c the cut size. This makes it well-suited for large graphs with small cuts, such as road graphs, which are our primary application. For road graphs we present an extensive experimental study demonstrating that FlowCutter outperforms the current state of the art both in terms of cut sizes as well as CCH performance.

Recommendations

• Graph bisection with Pareto-optimization
• Practical minimum cut algorithms
• Practical minimum cut algorithms
• Fast Approximate Graph Partitioning Algorithms
• Finding Separator Cuts in Planar Graphs within Twice the Optimal

Cites work

• A combined evolutionary search and multilevel optimisation approach to graph-partitioning
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• A note on two problems in connexion with graphs
• An exact combinatorial algorithm for minimum graph bisection
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Customizable contraction hierarchies
• Dijkstra's algorithm on-line
• Engineering multilevel overlay graphs for shortest-path queries
• Exact combinatorial branch-and-bound for graph bisection
• Generalized Nested Dissection
• Graph bisection with Pareto-optimization
• Graph Partitioning and Graph Clustering
• scientific article; zbMATH DE number 5610761 (Why is no real title available?)
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 1333614 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• Incidence matrices and interval graphs
• Inference in belief networks: A procedural guide
• Maximal Flow Through a Network
• Most balanced minimum cuts
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Nested Dissection of a Regular Finite Element Mesh
• Network flows. Theory, algorithms, and applications.
• Optimal node ranking of tree in linear time
• Optimal node ranking of trees
• Power of Natural Semijoins
• Preprocessing speed-up techniques is hard
• Search-space size in contraction hierarchies
• Some simplified NP-complete graph problems
• The analysis of a nested dissection algorithm
• The elimination form of the inverse and its application to linear programming
• The Evolution of the Minimum Degree Ordering Algorithm
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Treewidth: Structure and Algorithms

Cited in

(13)

• A predictive fault tolerant control method for qLPV systems subject to input faults and constraints
• ProCount: weighted projected model counting with graded project-join trees
• An analysis of the parameterized complexity of periodic timetabling
• Real-time traffic assignment using engineered customizable contraction hierarchies
• Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm
• Graph bisection with Pareto-optimization
• PACE Solver Description: Tree Depth with FlowCutter
• scientific article; zbMATH DE number 7764127 (Why is no real title available?)
• The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth.
• Fission: Practical algorithms for computing minimum balanced node separators
• Aspmc: new frontiers of algebraic answer set counting
• Solving decision theory problems with probabilistic answer set programming
• Scalable high-quality hypergraph partitioning

This page was built for publication: Graph bisection with Pareto optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4577953)