On the subgraph query problem

DOI10.1017/S0963548320000218zbMath1466.05192arXiv1911.04413MaRDI QIDQ4993118

Ryan Alweiss, Alexandre Moreira, Xiaoyu He, Chady Ben Hamida

Publication date: 15 June 2021

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

Hamilton cyclesqueriessubgraph query problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Ramsey theory (05D10) Eulerian and Hamiltonian graphs (05C45) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The longest path in a random graph
• Ramsey numbers of degenerate graphs
• Positional games
• Finding paths in sparse random graphs requires many queries
• Finding Hamilton cycles in random graphs with few queries
• Online Ramsey Numbers and the Subgraph Query Problem
• Cliques in random graphs
• Positional Games
• Finding cliques using few probes

This page was built for publication: On the subgraph query problem