Finding Hamilton cycles in random graphs with few queries

DOI10.1002/rsa.20679zbMath1352.05104arXiv1505.00730OpenAlexW2963302945MaRDI QIDQ2953694

No author found.

Publication date: 5 January 2017

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

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

zbMATH Keywords

random graphsHamiltonicityHamilton cyclesquerieseconomic

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Eulerian and Hamiltonian graphs (05C45)

Related Items (7)

Finding paths in sparse random graphs requires many queries ⋮ Finding a Hamilton cycle fast on average using rotations and extensions ⋮ An adversarial model for scheduling with testing ⋮ Online Ramsey Numbers and the Subgraph Query Problem ⋮ Finding a planted clique by adaptive probing ⋮ Extremal paths in inhomogenous random graphs ⋮ On the subgraph query problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Hamiltonian circuits in random graphs
• Hamilton cycles in a class of random directed graphs
• The phase transition in random graphs: A simple proof
• Finding paths in sparse random graphs requires many queries
• Hamilton cycles in 3-out
• Generating random graphs in biased Maker-Breaker games
• Avoiding small subgraphs in Achlioptas processes

This page was built for publication: Finding Hamilton cycles in random graphs with few queries