Minimum Cost Matching in a Random Graph with Random Costs

DOI10.1137/15M1047672zbMath1358.05257arXiv1504.00312OpenAlexW2963685107MaRDI QIDQ2968521

Tony Johansson, Alan M. Frieze

Publication date: 16 March 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1504.00312

zbMATH Keywords

random assignment problemparisi conjecture

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial optimization (90C27)

Related Items (3)

Random graphs: combinatorics, complex networks and disordered systems. Abstracts from the workshop held March 26--31, 2023 ⋮ Strong and weighted matchings in inhomogenous random graphs ⋮ The Effect of Adding Randomly Weighted Edges

Cites Work

• Unnamed Item
• Unnamed Item
• Random matching problems on the complete graph
• An easy proof of the \(\zeta (2)\) limit in the random assignment problem
• On the value of a random minimum spanning tree problem
• On Frieze's \(\zeta\) (3) limit for lengths of minimal spanning trees
• Asymptotics in the random assignment problem
• Random minimum length spanning trees in regular graphs
• A proof of Parisi's conjecture on the random assignment problem
• A note on random minimum length spanning trees
• Concentration of measure and isoperimetric inequalities in product spaces
• The ?(2) limit in the random assignment problem
• On the Expected Value of a Random Assignment Problem
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
• On the Length of a Random Minimum Spanning Tree
• 75.9 Euler’s Constant
• Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures

This page was built for publication: Minimum Cost Matching in a Random Graph with Random Costs