Query complexity of global minimum cut

DOI10.4230/LIPICS.APPROX/RANDOM.2021.6MaRDI QIDQ6090876zbMATH OpenFDO

Authors Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar

Publication date 20 November 2023

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

zbMATH Keywords

query complexityglobal mincut

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• Computing exact minimum cuts without knowing the graph
• On the Complexity of Finding an Unknown Cut Via Vertex Queries
• Quantum Query Complexity of Some Graph Problems
• Automata, Languages and Programming
• Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms

This page was built for publication: Query complexity of global minimum cut

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