Finding paths in sparse random graphs requires many queries

DOI10.1002/rsa.20680zbMath1352.05166arXiv1505.00734OpenAlexW2963995085MaRDI QIDQ2951884

No author found.

Publication date: 10 January 2017

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

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

zbMATH Keywords

pathsrandom graphsquerieseconomic

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Density (toughness, etc.) (05C42)

Related Items (5)

Finding Hamilton cycles in random graphs with few queries ⋮ An adversarial model for scheduling with testing ⋮ Online Ramsey Numbers and the Subgraph Query Problem ⋮ Finding a planted clique by adaptive probing ⋮ On the subgraph query problem

Cites Work

• Unnamed Item
• Unnamed Item
• The longest path in a random graph
• Une théorie combinatoire des séries formelles
• Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees
• Anatomy of the giant component: the strictly supercritical regime
• The phase transition in random graphs: A simple proof
• Finding Hamilton cycles in random graphs with few queries
• On tree census and the giant component in sparse random graphs
• The Galton-Watson process conditioned on the total progeny
• Routing complexity of faulty networks
• Proofs from THE BOOK

This page was built for publication: Finding paths in sparse random graphs requires many queries