Dez Algoritmos para o Problema-Sanduíche do Conjunto Homogêneo
Autores
|
4532 |
257,612
|
|
|
4533 |
257,612
|
Informações:
Publicações do PESC
Problemas-sanduíche são generalizações de problemas de reconhecimento em grafos, onde ao grafo de entrada - no qual investiga-se a existência de determinada propriedade - é oferecido um conjunto de arestas opcionais. Esta classe de problemas foi originalmente formulada com vistas a aplicações práticas em Biologia Computacional, mas sua abrangência já há muito não se encontra limitada àquele campo de pesquisa.
Muitos dos problemas-sanduíche abordados na literatura até este momento mostraram-se NP-completos. Dentre aqueles polinomiais, os mais interessantes - do ponto de vista da criação e análise de algoritmos - são os que não se sabe ainda resolver com eficiência semelhante à que se consegue para os problemas de reconhecimento clássicos que lhes são correspondentes. Pertence a este grupo o Problema-Sanduíche do Conjunto Homogêneo, tema desta tese, e para o qual apresentamos dez algoritmos distintos (oito de nossa autoria).
Acreditamos que este estudo venha não apenas permitir um bom entendimento do problema e suas peculiaridades, mas também fornecer um panorama amplamente ilustrativo - e, de certo modo, didático - do processo mais geral da gênese e refinamento de técnicas, na busca incessante pelo algoritmo ótimo.
Sandwich problems are generalizations of graph recognition problems, where the input instance graph | which will be investigated as for the existence of a certain property of is provided with a set of optional edges. This class of problems originally arose due to some Computational Biology practical applications, but it has long encompassed other research fields.
Many sandwich problems considered in the literature have been found to be NP-complete. Among those which are polynomial, the most interesting - from the standpoint of algorithm development and analysis | are those which are not yet solvable with an eficiency close to that achieved for their counterpart classical recognition problems. To this latter group belongs the Homogeneous Set Sandwich Problem, the subject of this thesis, and for which we present ten distinct algorithms (eight of them authored by us).
We believe that the text allows not only a thorough understanding of the problem and its singularities, but also provides the reader with a broad - and quite didactic - portrayal of the more general process of creation and refinement of techniques, in the constant search for the optimum algorithm.