Approximating small balanced vertex separators in almost linear time
From MaRDI portal
Publication:5919618
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
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)
Uses Software
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