Optimization Problems on Graphs with Independent Random Edge Weights
From MaRDI portal
Publication:3910569
DOI10.1137/0210024zbMath0461.05059MaRDI QIDQ3910569
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
random graphs; optimization problems; weighted graphs; normal distribution; greedy algorithms; Boole's inequality
Related Items
Combinational optimization problems for which almost every algorithm is asymptotically optimal, On the value of a random minimum spanning tree problem, On Frieze's \(\zeta\) (3) limit for lengths of minimal spanning trees, Maximal paths in random dynamic graphs