Linear time algorithms for finding sparsest cuts in various graph classes

DOI10.1016/J.ENDM.2007.01.039MaRDI QIDQ3439593zbMATH OpenOpenAlexFDO

Authors Paul Bonsma

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

zbMATH Keywords

graph classlinear timeminimum ratio cutsparsest cut

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• The complexity of finding uniform sparsest cuts in various graph classes
• Sparsest cuts and bottlenecks in graphs
• The complexity status of problems related to sparsest cuts
• Sparsest-cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
• Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem

Cites work

• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Depth-First Search and Linear Graph Algorithms
• scientific article; zbMATH DE number 1025912 (Why is no real title available?)
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Sparsest cuts and bottlenecks in graphs
• Sparsest cuts and concurrent flows in product graphs.

Cited in

(7)

• An O( n)-approximation algorithm for directed sparsest cut
• Sparsest cuts and concurrent flows in product graphs.
• Bounds on maximum concurrent flow in random bipartite graphs
• The complexity status of problems related to sparsest cuts
• Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• The complexity of finding uniform sparsest cuts in various graph classes

This page was built for publication: Linear time algorithms for finding sparsest cuts in various graph classes

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