The Distribution of Minimum-Weight Cliques and Other Subgraphs in Graphs with Random Edge Weights

DOI10.1137/17M1138303zbMath1406.60017arXiv1606.04925OpenAlexW2964017948WikidataQ125707541 ScholiaQ125707541MaRDI QIDQ4581213

Wesley Pegden, Gregory B. Sorkin, Alan M. Frieze

Publication date: 15 August 2018

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

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

zbMATH Keywords

networksrandom graphscliquesstatisticssubgraphs

Mathematics Subject Classification ID

Nonparametric hypothesis testing (62G10) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Approximations to statistical distributions (nonasymptotic) (62E17)

Related Items (2)

Successive shortest paths in complete graphs with random edge weights ⋮ Typical values of extremal-weight combinatorial structures with independent symmetric weights

Cites Work

• Two moments suffice for Poisson approximations: The Chen-Stein method
• Threshold functions for small subgraphs
• Unnamed Item
• Unnamed Item

This page was built for publication: The Distribution of Minimum-Weight Cliques and Other Subgraphs in Graphs with Random Edge Weights