Conditional Lower Bounds for All-Pairs Max-Flow

DOI10.1145/3212510zbMath1441.68076OpenAlexW2962913759MaRDI QIDQ4629955

Robert Krauthgamer, Ohad Trabelsi

Publication date: 28 March 2019

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7426/

zbMATH Keywords

strong exponential time hypothesishardness in Pconditional lower boundsall-pairs maximum flow

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

Empirical study on sufficient numbers of minimum cuts in strongly connected directed random graphs ⋮ The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance ⋮ Unnamed Item ⋮ A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: Conditional Lower Bounds for All-Pairs Max-Flow