Deterministic Global Minimum Cut Using Cut Queries
En palabras de los autores
Finding a global minimum cut in an unweighted graph is a fundamental task in the cut-query model. While there exists a randomized algorithm for this task using queries, known deterministic algorithms use queries. We improve upon this result and give a simple deterministic algorithm that finds a global minimum cut using cut queries, which equals in the worst case, where is the minimum degree of the graph. The key ingredient in our approach is an efficient maximum -flow algorithm, for the case when the minimum -cut has value at most .
Resultado principalEl resumen no menciona limitaciones.
Apareció: lunes, 19 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: Accepted at SOSA 2027