Linear time algorithms for finding sparsest cuts in various graph classes
From MaRDI portal
Publication:3439593
DOI10.1016/j.endm.2007.01.039zbMath1293.05364OpenAlexW2139531571MaRDI QIDQ3439593
Publication date: 29 May 2007
Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.endm.2007.01.039
Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (3)
The complexity of finding uniform sparsest cuts in various graph classes ⋮ Bounds on maximum concurrent flow in random bipartite graphs ⋮ The Complexity Status of Problems Related to Sparsest Cuts
Cites Work
- Unnamed Item
- Sparsest cuts and bottlenecks in graphs
- Sparsest cuts and concurrent flows in product graphs.
- A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Depth-First Search and Linear Graph Algorithms
This page was built for publication: Linear time algorithms for finding sparsest cuts in various graph classes