Query complexity of global minimum cut

DOI10.4230/LIPICS.APPROX/RANDOM.2021.6arXiv2007.09202MaRDI QIDQ6090876FDOQ6090876

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

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

zbMATH Keywords

query complexityglobal mincut

Mathematics Subject Classification ID

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

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)