Approximating small balanced vertex separators in almost linear time

DOI10.1007/s00453-018-0490-xzbMath1430.68181OpenAlexW2886646512MaRDI QIDQ5919618

Roger Wattenhofer, Sebastian F. Brandt

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

parallel processinglinear-time algorithmbalanced vertex separator

Mathematics Subject Classification ID

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

Uses Software

• Pregel
• PowerGraph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized graph separation problems
• Finding good approximate vertex and edge partitions is NP-hard
• Finding small balanced separators
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• A separator theorem for graphs of bounded genus
• Maximal Flow Through a Network
• Constant factor approximation of vertex-cuts in planar graphs
• Improved approximation algorithms for minimum-weight vertex separators
• A Separator Theorem for Planar Graphs
• Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications

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