7 citations · 14 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…
Parameterized Exact and Approximation Algorithms for Maximum -Set Cover and Related Satisfiability Problems
Edouard Bonnet, Vangelis Th. Paschos, Florian Sikora
Given a family of subsets over a set of elements~ and two integers~ and~, Max k-Set Cover consists of finding a subfamily~ of…
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…