Paths, Trees, and Flowers

By J. Edmonds. 1965

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Frank-Wolfe Algorithms for Saddle Point Problems (2016, methodology): “Edmonds (1965) showed that any subgraph forming a triangle can contain at most one edge of any perfect matching.”
Network optimization : continuous and discrete models (1998, methodology): “Edmonds and Karp [1972] developed the first polynomial algorithm, using a version of the out-of-kilter method (a variant of the primaldual method to be discussed in Chapter 6) that employed cost and capacity scaling. Subsequently, in the late 70s, polynomial algorithms for the general linear program”
Sparse Blossom: correcting a million errors per core second with minimum-weight matching (2023, unknown): “We will now give an overview of the original unweighted version the blossom algorithm, which finds a maximum cardinality matching (as introduced by Edmonds in [Edm65b]).”
Graph Factors and Matching Extensions (2009, background): “Gallai (1964) and Edmonds (1965), independently, investigated a canonical decomposition of arbitrary graphs in terms of its maximum matchings and thus revealed the structure of graphs related to matchings.”
The Ellipsoid Method: A Survey (1980, methodology): “provide an alternative to the algorithms of Edmonds [1968], and of Lawler [1976] for the (2-) matroid intersection problem.”
Communication-Efficient Decentralized Learning with Sparsification and Adaptive Peer Selection (2020, methodology): “Here, we exploit the blossom algorithm [33] to solve the problem of maximum match in a general graph.”
Online Matching and Ad Allocation (2013, methodology): “Edmonds [42] presented the Blossom algorithm to compute a maximum matching in a general graph in polynomial time.”
Graph construction and b-matching for semi-supervised learning (2009, background): “…problem .nds a subgraph of G with maximum weight while constraining the number of edges for each vertex to equal b. b-matching is a direct generalization of the maximum weight unipartite matching problem(b = 1) which is solved by Edmonds algorithm inpolynomial time O(n3) (Edmonds, 1965).”
Assembly of long, error-prone reads using repeat graphs (2018, methodology): “Flye thus applies Edmonds’ algorithm (Edmonds, 1965) to find a maximum weight matching in the transition graph and uses this matching for untangling the contracted repeat graph.”
Image Segmentation with Ratio Cut (2003, methodology): “The second reduction, from minimum ratio cycle to negative-cost cycle, uses the same binary and linear search techniques, discussed by Ahuja et al. [13, pp. 150-157], where they are used to find the minimum ratio cycle in a directed graph.”
Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges (2007, methodology): “For example, using Edmond’s maximum-matching algorithm [4], [20] shows that a national pairwise-exchange market (using length-2 cycles only) would result in more transplants, reduced waiting time, and savings of $750 million in heath care costs over 5 years.”
Efficient algorithms for finding maximum matching in graphs (1986, methodology): “Edmonds' idea (Edmonds 1965a) was to shrink B: Replace it by a single supervertex B and replace the set A of edges incident with vertices in B by the set A' = ((B, j) ] j 4 B, 3 (i, j) E A].”
Helios: a hybrid electrical/optical switch architecture for modular data centers (2010, methodology): “We chose the Edmonds algorithm [7] to compute the maxweighted matching because it is optimal, runs in polynomial time (O(n(3)) for our bipartite graph), and because there are libraries readily available.”
Quantum error correction: an introductory guide (2019, methodology): “For surface codes, a technique known as minimum weight perfect matching (MWPM) can be used for decoding, which works by identifying error chains between positive syndrome measurements [55,56].”
Surface code quantum computing by lattice surgery (2011, unknown): “[19, 20, 21].”