The diameter of randomly perturbed digraphs and some applications

DOI10.1002/rsa.20172zbMath1125.05094OpenAlexW2639104656WikidataQ57401500 ScholiaQ57401500MaRDI QIDQ5297137

Abraham D. Flaxman, Alan M. Frieze

Publication date: 18 July 2007

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

Full work available at URL: https://doi.org/10.1002/rsa.20172

zbMATH Keywords

random digraphsconnectivity algorithms

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (5)

Smoothed Analysis of Local Search Algorithms ⋮ On the average path length of a cycle plus random edges ⋮ Smoothed Analysis on Connected Graphs ⋮ Shortcutting directed and undirected networks with a degree constraint ⋮ Smoothed analysis of balancing networks

Cites Work

• Unnamed Item
• Unnamed Item
• Typical properties of winners and losers in discrete optimization
• Undirected ST-connectivity in log-space
• Smoothed analysis of algorithms
• Algorithms and Data Structures

This page was built for publication: The diameter of randomly perturbed digraphs and some applications