Successive shortest paths in complete graphs with random edge weights

DOI10.1002/rsa.20962zbMath1454.05060arXiv1911.01151OpenAlexW3097541195MaRDI QIDQ3386534

Balázs F. Mezei, Stefanie Gerke, Gregory B. Sorkin

Publication date: 5 January 2021

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

shortest pathrobust optimizationDijkstra's algorithmminimum-cost flowoptimization in random structuressecond-cheapest structure

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Combinatorial probability (60C05) Distance in graphs (05C12) Signed and weighted graphs (05C22)

Related Items (2)

Successive minimum spanning trees ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unoriented first-passage percolation on the \(n\)-cube
• Short paths for first passage percolation on the complete graph
• The mean field traveling salesman and related problems
• The median of the Poisson distribution
• Uniform recursive trees: branching structure and simple random downward walk
• 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
• Random minimum length spanning trees in regular graphs
• Tail bounds for sums of geometric and exponential variables
• The smallest uniform upper bound on the distance between the mean and the median of the binomial and Poisson distributions
• Weak disorder asymptotics in the stochastic mean-field model of distance
• The ?(2) limit in the random assignment problem
• First Passage Percolation on the Erdős–Rényi Random Graph
• Mean, Median and Mode in Binomial Distributions
• On the Medians of Gamma Distributions and an Equation of Ramanujan
• The Distribution of Minimum-Weight Cliques and Other Subgraphs in Graphs with Random Edge Weights
• On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights

This page was built for publication: Successive shortest paths in complete graphs with random edge weights