{
  "id": "enwiki-001271330582",
  "slug": "edmonds-algorithm",
  "title": "Edmonds' algorithm",
  "qid": "",
  "lead": "In graph theory, Edmonds' algorithm or Chu–Liu/Edmonds' algorithm is an algorithm for finding a spanning arborescence of minimum weight (sometimes called an optimum branching). It is the directed analog of the minimum spanning tree problem. The algorithm was proposed independently first by Yoeng-Jin Chu and Tseng-Hong Liu (1965) and then by Jack Edmonds (1967).",
  "body": "In graph theory, Edmonds' algorithm or Chu–Liu/Edmonds' algorithm is an algorithm for finding a spanning arborescence of minimum weight (sometimes called an optimum branching). It is the directed analog of the minimum spanning tree problem. The algorithm was proposed independently first by Yoeng-Jin Chu and Tseng-Hong Liu (1965) and then by Jack Edmonds (1967). ==Algorithm== ===Description=== The algorithm takes as input a directed graph D = \\langle V, E \\rangle where V is the set of nodes and E is the set of directed edges, a distinguished vertex r \\in V called the root, and a real-valued weight w(e) for each edge e \\in E . It returns a spanning arborescence A rooted at r of minimum weight, where the weight of an arborescence is defined to be the sum of its edge weights, w(A) = \\sum_{e \\in A}{w(e)} . The algorithm has a recursive description. Let f(D, r, w) denote the function which returns a spanning arborescence rooted at r of minimum weight. We first remove any edge from E whose destination is r . We may also replace any set of parallel edges (edges between the same pair of vertices in the same direction) by a single edge with weight equal to the minimum of the weights of these parallel edges. Now, for each node v other than the root, find the edge incoming to v of lowest weight (with ties broken arbitrarily). Denote the source of this edge by \\pi(v) . If the set of edges P = \\{(\\pi(v),v) \\mid v \\in V \\setminus \\{ r \\} \\} does not contain any cycles, then f(D,r,w) = P . Otherwise, P contains at least one cycle. Arbitrarily choose one of these cycles and call it C . We now define a new weighted directed graph D^\\prime = \\langle V^\\prime, E^\\prime \\rangle in which the cycle C is \"contracted\" into one node as follows: The nodes of V^\\prime are the nodes of V not in C plus a new node denoted v_C . If (u,v) is an edge in E with u\\notin C and v\\in C (an edge coming into the cycle), then include in E^\\prime a new edge e = (u, v_C) , and define w^\\prime(e) = w(u,v) - w(\\pi(v),v) . If (u,v) is an edge in E with u\\in C and v\\notin C (an edge going away from the cycle), then include in E^\\prime a new edge e = (v_C, v) , and define w^\\prime(e) = w(u,v) . If (u,v) is an edge in E with u\\notin C and v\\notin C (an edge unrelated to the cycle), then include in E^\\prime a new edge e = (u, v) , and define w^\\prime(e) = w(u,v) . For each edge in E^\\prime , we remember which edge in E it corresponds to. Now find a minimum spanning arborescence A^\\prime of D^\\prime using a call to f(D^\\prime, r,w^\\prime) . Since A^\\prime is a spanning arborescence, each vertex has exactly one incoming edge. Let (u, v_C) be the unique incoming edge to v_C in A^\\prime . This edge corresponds to an edge (u,v) \\in E with v \\in C . Remove the edge (\\pi(v),v) from C , breaking the cycle. Mark each remaining edge in C . For each edge in A^\\prime , mark its corresponding edge in E . Now we define f(D, r, w) to be the set of marked edges, which form a minimum spanning arborescence. Observe that f(D, r, w) is defined in terms of f(D^\\prime, r, w^\\prime) , with D^\\prime having strictly fewer vertices than D . Finding f(D, r, w) for a single-vertex graph is trivial (it is just D itself), so the recursive algorithm is guaranteed to terminate. ==Running time== The running time of this algorithm is O(EV) . A faster implementation of the algorithm due to Robert Tarjan runs in time O(E \\log V) for sparse graphs and O(V^2) for dense graphs. This is as fast as Prim's algorithm for an undirected minimum spanning tree. In 1986, Gabow, Galil, Spencer, and Tarjan produced a faster implementation, with running time O(E + V \\log V) .",
  "categories": [
    "23118434",
    "23221441",
    "23603337"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1271330582",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1737642684.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001271330582",
    "type": "webpage",
    "title": "Edmonds' algorithm",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/edmonds-algorithm",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          15
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          15
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001271330582",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1271330582",
    "note": "Immutable snapshot enwiki-001271330582"
  }
}