Approximating small balanced vertex separators in almost linear time

DOI10.1007/S00453-018-0490-XMaRDI QIDQ5919618zbMATH OpenOpenAlexFDO

Authors Sebastian F. Brandt, Roger Wattenhofer

Publication date 10 September 2019

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-018-0490-x

zbMATH Keywords

balanced vertex separatorlinear-time algorithmparallel processing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• Approximating small balanced vertex separators in almost linear time
• Finding small balanced separators
• A linear-time algorithm to find a separator in a graph excluding a minor
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Fast Approximate Graph Partitioning Algorithms

Cites work

• A linear-time algorithm to find a separator in a graph excluding a minor
• A separator theorem for graphs of bounded genus
• A Separator Theorem for Planar Graphs
• Constant factor approximation of vertex-cuts in planar graphs
• Finding good approximate vertex and edge partitions is NP-hard
• Finding small balanced separators
• scientific article; zbMATH DE number 5485455 (Why is no real title available?)
• scientific article; zbMATH DE number 3946182 (Why is no real title available?)
• scientific article; zbMATH DE number 1261808 (Why is no real title available?)
• scientific article; zbMATH DE number 6472641 (Why is no real title available?)
• Improved approximation algorithms for minimum-weight vertex separators
• Maximal Flow Through a Network
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Parameterized graph separation problems
• Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications

Cited in

(9)

• On classes of graphs with strongly sublinear separators
• Partitioning a graph into small pieces with applications to path transversal
• A linear-time algorithm to find a separator in a graph excluding a minor
• Finding small balanced separators
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
• Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator
• Approximating small balanced vertex separators in almost linear time
• Faster min-cost flow and approximate tree decomposition on bounded treewidth graphs

Describes a project that uses

Uses Software

• Pregel
• PowerGraph

This page was built for publication: Approximating small balanced vertex separators in almost linear time

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