@inproceedings{f4e7755415864ecda40a59b102784303,
title = "Quantum algorithms for matching and network flows",
abstract = "We present quantum algorithms for some graph problems: finding a maximal bipartite matching in time O(n√m log n), finding a maximal non-bipartite matching in time O(n 2(√m/n+log n) log n), and finding a maximal flow in an integer network in time O(min(n 7/6√m · U 1/3, √nUm) log n), where n is the number of vertices, m is the number of edges, and U ≤ n 1/4 is an upper bound on the capacity of an edge.",
author = "Andris Ambainis and Robert {\v S}palek",
year = "2006",
doi = "10.1007/11672142\_13",
language = "English",
isbn = "3540323015",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "172--183",
booktitle = "STACS 2006",
note = "STACS 2006: 23rd Annual Symposium on Theoretical Aspects of Computer Science, Proceedings ; Conference date: 23-02-2006 Through 25-02-2006",
}