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

DOI10.1137/130916357zbMath1294.05140arXiv1207.6549OpenAlexW2158624781MaRDI QIDQ4979844

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

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 transformgenerating functionsasymptotic expansionrandom graphsgraph algorithmspantograph equationsaddle-point method

Mathematics Subject Classification ID

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

Related Items (3)

On comparing algorithms for the maximum clique problem ⋮ Average-case complexity of a branch-and-bound algorithm for \textsc{Min Dominating Set} ⋮ 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