Computing optimal solutions for the MIN 3-SET COVERING problem

Della Croce, Federico; Paschos, Vangelis

Della Croce, Federico; Paschos, Vangelis (2005), Computing optimal solutions for the MIN 3-SET COVERING problem, in Du, Ding-Zhu; Deng, Xiaotie, Algorithms and Computation 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings, Springer : Berlin, p. 685-692. http://dx.doi.org/10.1007/11602613_69

Type

Communication / Conférence

Date

2005

Conference title

16th International Symposium on Algorithms and Computation (ISAAC'05)

Conference date

2005-12

Conference city

Sanya (Hainan)

Conference country

Chine

Book title

Algorithms and Computation 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings

Book author

Du, Ding-Zhu; Deng, Xiaotie

Publisher

Springer

Series title

Lecture Notes in Computer Science

Series number

3827

Published in

Berlin

ISBN

978-3-540-30935-2

Number of pages

1190

Pages

685-692

Abstract (EN)

We consider min set covering when the subsets are constrained to have maximum cardinality three. We propose an exact algorithm whose worst case complexity is bounded above by O*(1.4492n).

Subjects / Keywords

Algorithms