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

asymptotic expansiongenerating functionsgraph algorithmsLaplace transformpantograph equationrandom graphssaddle-point method

Mathematics Subject Classification ID

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

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)

• On comparing algorithms for the maximum clique problem
• An analytic approach to the asymptotic variance of trie statistics and related structures
• 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}

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)