Random assignment and shortest path problems

MaRDI QIDQ3574980zbMATH OpenFDO

Authors Johan Wästlund

Publication date 5 July 2010

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAG0102/0.html

zbMATH Keywords

random treeminimum matching

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Stochastic scheduling theory in operations research (90B36)

Recommendations

• Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
• The (2) limit in the random assignment problem
• scientific article; zbMATH DE number 1802784
• Constructive bounds and exact expectations for the random assignment problem
• An easy proof of the \(\zeta (2)\) limit in the random assignment problem

Cited in

(6)

• Edge flows in the complete random-lengths network
• Random assignment problems
• Degree distribution of shortest path trees and bias of network sampling algorithms
• First passage percolation on random graphs with finite mean degrees
• A combinatorial problem on a directed graph
• Extreme value theory, Poisson-Dirichlet distributions, and first passage percolation on random networks

This page was built for publication: Random assignment and shortest path problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3574980)