Analysis of an Exhaustive Search Algorithm in Random Graphs and the n^{c\log n}-Asymptotics

DOI10.1137/130916357zbMATH Open1294.05140arXiv1207.6549OpenAlexW2158624781MaRDI QIDQ4979844FDOQ4979844

Authors: Cyril Banderier, Hsien-Kuei Hwang, Vlady Ravelomanana, Vytas Zacharovas 

Publication date: 19 June 2014

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We analyze the cost used by a naive exhaustive search algorithm for finding a maximum independent set in random graphs under the usual G_{n,p} -model where each possible edge appears independently with the same probability p. The expected cost turns out to be of the less common asymptotic order n^{clog n}, which we explore from several different perspectives. Also we collect many instances where such an order appears, from algorithmics to analysis, from probability to algebra. The limiting distribution of the cost required by the algorithm under a purely idealized random model is proved to be normal. The approach we develop is of some generality and is amenable for other graph algorithms.

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

Recommendations

• Analysis of Algorithms on the Cores of Random Graphs
• An almost-greedy search on random binary vectors and random graphs
• On the asymptotics of constrained exponential random graphs
• Algorithms and complexity results for finding graphs with extremal Randić index
• Asymptotic theory of greedy approximations to minimal k-point random graphs
• A detailed investigation into near degenerate exponential random graphs
• Analysis of an iterated local search algorithm for vertex cover in sparse random graphs
• scientific article; zbMATH DE number 3876622
• scientific article; zbMATH DE number 3854438
• scientific article; zbMATH DE number 1890147

zbMATH Keywords

Laplace transformasymptotic expansiongenerating functionsgraph algorithmspantograph equationrandom graphssaddle-point method

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial probability (60C05) Asymptotic enumeration (05A16)

Cited In (4)

• Average-case complexity of a branch-and-bound algorithm for \textsc{Min Dominating Set}
• An almost-greedy search on random binary vectors and random graphs
• An analytic approach to the asymptotic variance of trie statistics and related structures
• On comparing algorithms for the maximum clique problem

This page was built for publication: Analysis of an Exhaustive Search Algorithm in Random Graphs and the $n^{c\log n}$-Asymptotics

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