Ten algorithms for the Homogeneous Set Sandwich Problem - Sá, Vinícius Gusmão Pereira de (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC); 2007: Anais do XX Concurso de Teses e Dissertações, 2007)
This thesis presents state-of-the-art results in two areas of increasing relevance over recent years: graph sandwich problems and randomized algorithms. Sandwich problems are generalizations of recognition problems where the input graph is provided with a set of optional edges. The Homogeneous Set Sandwich Problem, subject of this thesis, is one of the few polynomial-time sandwich problems known to date. Following the first two algorithms (not ours) published for it (one of which proved incorrect in [Sá 2003]), we introduce a series of eight faster algorithms, among deterministic and randomized ones. The text shows a comprehensive range of continuously refined techniques, culminating at the establishment of the problem’s currently accepted upper bound.