13 citations · 17 across the 3 of their papers we have counts for
3 papers
cs.CC2015★ 2 cited
Average-case complexity of a branch-and-bound algorithm for maximum independent set, under the random model
N. Bourgeois, R. Catellier, T. Denat +1
We study average-case complexity of branch-and-bound for maximum independent set in random graphs under the distribution. In this model every pair of ver…
cs.CC2013★ 2 cited
Playing with parameters: structural parameterization in graphs
Nicolas Bourgeois, Konrad K. Dabrowski, Marc Demange +1
When considering a graph problem from a parameterized point of view, the parameter chosen is often the size of an optimal solution of this problem (the "standard" parameter). A nat…
cs.DS2009★ 13 cited
Fast algorithms for min independent dominating set
Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos
We first devise a branching algorithm that computes a minimum independent dominating set on any graph with running time O*(2^0.424n) and polynomial space. This improves the O*(2^0.…