Sparsest cuts and concurrent flows in product graphs.

DOI10.1016/S0166-218X(03)00439-6zbMath1036.90023OpenAlexW2033961184MaRDI QIDQ1427176

Paul Bonsma

Publication date: 14 March 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(03)00439-6

zbMATH Keywords

Product graphBottleneck graphConcurrent flowSparsest cut

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Graph theory (05C99)

Related Items (5)

Euclidean prize-collecting Steiner forest ⋮ The complexity of finding uniform sparsest cuts in various graph classes ⋮ The Complexity Status of Problems Related to Sparsest Cuts ⋮ Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs ⋮ Linear time algorithms for finding sparsest cuts in various graph classes

Cites Work

• Sparsest cuts and bottlenecks in graphs
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• The maximum concurrent flow problem
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Sparsest cuts and concurrent flows in product graphs.