scientific article; zbMATH DE number 7204472

DOI10.4230/LIPICS.ICALP.2017.20MaRDI QIDQ5111350zbMATH OpenFDO

Authors Robert Krauthgamer, Ohad Trabelsi

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1702.05805

zbMATH Keywords

all-pairs maximum flowconditional lower boundshardness in Pstrong exponential time hypothesis

Mathematics Subject Classification ID

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

Recommendations

• Conditional Lower Bounds for All-Pairs Max-Flow
• scientific article; zbMATH DE number 177817
• An o(n^3 )-Time Maximum-Flow Algorithm

Cited in

(4)

• Conditional Lower Bounds for All-Pairs Max-Flow
• Faster algorithms for all-pairs bounded min-cuts
• New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
• New algorithms and lower bounds for all-pairs max-flow in undirected graphs

This page was built for publication:

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