scientific article; zbMATH DE number 1380616

DOI10.1002/(SICI)1098-2418(1999010)14:1%3C87::AID-RSA5%3E3.0.CO;2-OMaRDI QIDQ4705352zbMATH OpenFDO

Authors Andrei Broder, Eli Upfal, Alan Frieze

Publication date 19 December 1999

zbMATH Keywords

Poisson processesalgorithmrandom walkscommunication networksexpander graphspathmulticommodity flowcircuit switching

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Recommendations

• scientific article; zbMATH DE number 1559568
• scientific article; zbMATH DE number 1301961
• Random walks which prefer unvisited edges, exploring high girth even degree expanders in linear time
• Random walks which prefer unvisited edges: exploring high girth even degree expanders in linear time
• Maximal paths in random dynamic graphs
• Dynamic single-source shortest paths in Erdős-Rényi random graphs
• The optimal path in an Erdős-Rényi random graph
• Periodic dynamic graphs. Random walks problem and the shortest path

Cites work

• Approximate counting, uniform generation and rapidly mixing Markov chains
• Eigenvalues and expanders
• Existence and Construction of Edge-Disjoint Paths on Expander Graphs
• Explicit construction of linear sized tolerant networks
• Graph minors. XIII: The disjoint paths problem
• Ramanujan graphs

Cited in

(3)

• Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
• Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
• scientific article; zbMATH DE number 1559568 (Why is no real title available?)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4705352)