The Homogeneous Set Sandwich Problem - Sá, Vinícius Gusmão Pereira de (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC); 2004: Anais do XVII Concurso de Teses e Dissertações, 2004)
Homogeneous sets have proved useful for the construction of graph decomposition procedures. Sandwich graphs are obtained from two pre-defined graphs which provide them with both mandatory and optional edges. Given such a pair of graphs, the Homogeneous Set Sandwich Problem (HSSP) searches for a sandwich graph which contains a homogeneous set. This thesis presents the development of techniques for solving the HSSP and culminates in the correction of the established upper bounds for its time complexity. Such results comprise the description of thoroughly depicted counterexamples which prove the incorrectness of the (so far) best published HSSP algorithm, along with the proposal of a new, faster algorithm.