Fission: Practical algorithms for computing minimum balanced node separators

DOI10.1142/S1793830922500483MaRDI QIDQ6115756zbMATH OpenOpenAlexFDO

Authors Johannes Blum, Ruoying Li, Sabine Storandt

Publication date 13 July 2023

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s1793830922500483

zbMATH Keywords

exact algorithmgraph partitioningcontraction hierarchiesbalanced node separator

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Graph bisection with Pareto optimization
• Graph bisection with Pareto-optimization
• Fast Approximate Graph Partitioning Algorithms
• Finding small balanced separators
• Engineering planar separator algorithms

Cites work

• scientific article; zbMATH DE number 5485558 (Why is no real title available?)
• scientific article; zbMATH DE number 5734722 (Why is no real title available?)
• scientific article; zbMATH DE number 4060712 (Why is no real title available?)
• scientific article; zbMATH DE number 176254 (Why is no real title available?)
• scientific article; zbMATH DE number 7651159 (Why is no real title available?)
• A Polylogarithmic Approximation of the Minimum Bisection
• A framework for solving VLSI graph layout problems
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
• Breaking the multicommodity flow barrier for o(√log n)-approximations to sparsest cut
• Computing all-pairs shortest paths by leveraging low treewidth
• Contraction and Treewidth Lower Bounds
• Customizable contraction hierarchies
• Distributed Evolutionary Graph Partitioning
• Engineering multilevel graph partitioning algorithms
• Engineering planar separator algorithms
• Finding good approximate vertex and edge partitions is NP-hard
• Finding small balanced separators
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Graph bisection with Pareto optimization
• Graph clustering
• Graph partitioning
• Graph partitioning using single commodity flows
• High quality graph partitioning
• High-performance multi-level routing
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Measuring the vulnerability for classes of intersection graphs
• Multiway cuts in node weighted graphs
• Nested Dissection of a Regular Finite Element Mesh
• Parameterized graph separation problems
• Search-space size in contraction hierarchies
• Treewidth lower bounds with brambles

This page was built for publication: Fission: Practical algorithms for computing minimum balanced node separators

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