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

DOI10.1137/130916357MaRDI QIDQ4979844zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cited in

(4)

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

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)