Optimization Problems on Graphs with Independent Random Edge Weights

DOI10.1137/0210024zbMath0461.05059OpenAlexW1965258184MaRDI QIDQ3910569

George S. Lueker

Publication date: 1981

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://escholarship.org/uc/item/6wf1f973

zbMATH Keywords

random graphsoptimization problemsweighted graphsnormal distributiongreedy algorithmsBoole's inequality

Mathematics Subject Classification ID

Combinatorial probability (60C05) Graph theory (05C99) Algorithms in computer science (68W99)

Related Items (4)

On Frieze's \(\zeta\) (3) limit for lengths of minimal spanning trees ⋮ Maximal paths in random dynamic graphs ⋮ Combinational optimization problems for which almost every algorithm is asymptotically optimal ⋮ On the value of a random minimum spanning tree problem

This page was built for publication: Optimization Problems on Graphs with Independent Random Edge Weights