Paper Info
Title
Russian doll search for the Steiner triple covering problem.
Abstract
Russian doll search is applied to finding maximum independent sets in hypergraphs, focusing on a particular subproblem of the hitting set problem, the Steiner triple covering problem. An instance denoted A 135 is solved considerably faster with Russian doll search than with integer linear programming and a state-of-the-art optimization tool (using otherwise a similar established approach to split the problem into subproblems). In addition, the improvement in speed makes it possible to carry out a search proving that all optimal solutions for A 135 are isomorphic.
Year
DOI
Venue
2011
10.1007/s11590-010-0225-7
Optimization Letters
Keywords
Field
DocType
Hitting set problem, Russian doll search, Set covering problem, Steiner triple system
Set cover problem,Monad (category theory),Combinatorics,Constraint graph,Integer programming,Isomorphism,Mathematics,Steiner system
Journal
Volume
Issue
ISSN
5
4
1862-4480
Citations 
PageRank 
References 
6
0.49
11
Authors
2
Name
Order
Citations
PageRank
Patric R. J. Östergård160970.61
Vesa P. Vaskelainen291.25