{
  "id": "quant-ph/0508205",
  "version": "v2",
  "published": "2005-08-27T06:06:38.000Z",
  "updated": "2005-09-08T12:42:53.000Z",
  "title": "Quantum Algorithms for Matching and Network Flows",
  "authors": [
    "Andris Ambainis",
    "Robert Spalek"
  ],
  "comment": "13 pages, v2: added an Omega(n^2) lower bound for network flows",
  "categories": [
    "quant-ph"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2005-09-08T12:42:53.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "quantum algorithms",
      "network flows",
      "upper bound",
      "maximal flow",
      "graph problems"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005quant.ph..8205A"
    }
  }
}