Quantum Algorithms for Matching and Network Flows
| dc.creator | Ambainis, Andris | |
| dc.creator | Spalek, Robert | |
| dc.date | 2005-08-27 | |
| dc.date | 2005-09-08 | |
| dc.date.accessioned | 2026-07-07T06:13:26Z | |
| dc.date.available | 2026-07-07T06:13:26Z | |
| dc.description | We present quantum algorithms for the following graph problems: finding a maximal bipartite matching in time O(n sqrt{m+n} log n), finding a maximal non-bipartite matching in time O(n^2 (sqrt{m/n} + log n) log n), and finding a maximal flow in an integer network in time O(min(n^{7/6} sqrt m * U^{1/3}, sqrt{n U} m) 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. | |
| dc.description | 13 pages, v2: added an Omega(n^2) lower bound for network flows | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0508205 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0508205 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/93102 | |
| dc.subject | Quantum Physics | |
| dc.title | Quantum Algorithms for Matching and Network Flows | |
| dc.type | text |