Name
Title | ||
|---|---|---|
Average-case complexity of a branch-and-bound algorithm for maximum independent set, under the $\mathcal{G}(n,p)$ random model |
Abstract | ||
|---|---|---|
We study average-case complexity of branch-and-bound for maximum independent set in random graphs under the $\mathcal{G}(n,p)$ distribution. In this model every pair $(u,v)$ of vertices belongs to $E$ with probability $p$ independently on the existence of any other edge. We make a precise case analysis, providing phase transitions between subexponential and exponential complexities depending on the probability $p$ of the random model. |
Year | Venue | Field |
|---|---|---|
2015 | CoRR | Discrete mathematics,Average-case complexity,Combinatorics,Branch and bound,Random graph,Exponential function,Vertex (geometry),Phase transition,Independent set,Mathematics,Computational complexity theory |
DocType | Volume | Citations |
Journal | abs/1505.04969 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicolas Bourgeois | 1 | 99 | 7.96 |
| r catellier | 2 | 0 | 0.34 |
| t denat | 3 | 0 | 0.34 |
| Vangelis Th. Paschos | 4 | 124 | 11.68 |