7 citations · 12 across the 4 of their papers we have counts for
4 papers
Average-case complexity of a branch-and-bound algorithm for min dominating set
Tom Denat, Ararat Harutyunyan, Vangelis Th. Paschos
The average-case complexity of a branch-and-bound algorithms for Minimum Dominating Set problem in random graphs in the G(n,p) model is studied. We identify phase transitions betwe…
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…
A 0.821-ratio purely combinatorial algorithm for maximum -vertex cover in bipartite graphs
Edouard Bonnet, Bruno Escoffier, Vangelis Paschos +1
Our goal in this paper is to propose a \textit{combinatorial algorithm} that beats the only such algorithm known previously, the greedy one. We study the polynomial approximation o…
Fast Algorithms for Max Independent Set in Graphs of Small Average Degree
Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos +1
Max Independent Set (MIS) is a paradigmatic problem in theoretical computer science and numerous studies tackle its resolution by exact algorithms with non-trivial worst-case compl…