Finding Hamilton cycles in random graphs with few queries | Zendy

Ferber Asaf | Zendy; Krivelevich Michael | Zendy; Sudakov Benny | Zendy; Vieira Pedro | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Finding Hamilton cycles in random graphs with few queries

Author(s) -

Ferber Asaf,

Krivelevich Michael,

Sudakov Benny,

Vieira Pedro

Publication year - 2016

Publication title -

random structures and algorithms

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.314

H-Index - 69

eISSN - 1098-2418

pISSN - 1042-9832

DOI - 10.1002/rsa.20679

Subject(s) - adjacency list , random graph , combinatorics , struct , property (philosophy) , hamiltonian path , mathematics , order (exchange) , discrete mathematics , computer science , graph , philosophy , epistemology , finance , economics , programming language

We introduce a new setting of algorithmic problems in random graphs, studying the minimum number of queries one needs to ask about the adjacency between pairs of vertices of G ( n , p ) in order to typically find a subgraph possessing a given target property. We show that if p ≥ ln n + ln ln n + ω ( 1 ) n , then one can find a Hamilton cycle with high probability after exposing ( 1 + o ( 1 ) ) n edges. Our result is tight in both p and the number of exposed edges. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 635–668, 2016

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research