Minimum Cost Matching in a Random Graph with Random Costs.

Alan M. Frieze Tony Johansson

Published in: SIAM J. Discret. Math. (2017)

Keyphrases

minimum cost
random graphs
undirected graph
np hard
linear relaxation
approximation algorithms
network flow
network flow problem
spanning tree
graph theoretic
capacity constraints
matching algorithm
network simplex algorithm
phase transition
graph matching
computational complexity
edit operations