O Problema-Sanduíche para Conjuntos Homogêneos em Grafos
Autores
|
2278 |
257,612
|
|
|
2279 |
257,612
|
Informações:
Publicações do PESC
0 conceito de conjunto homogêneo é de grande valia para a elaboração de procedimentos de decomposição de grafos. Grafos-sanduíche são obtidos a partir de dois grafos pré-definidos que lhes emprestam arestas, entre obrigatórias e opcionais. No Problema-Sanduíche para Conjuntos Homogêneos (PSCH), deseja-se descobrir se há, para um par de grafos dado, um grafo-sanduíche que possua algum conjunto homogêneo. Não obstante haver algoritmos lineares para a determinação de conjuntos homogêneos em um grafo isolado, o PSCH continua a ser objeto de pesquisa, dadas as altas complexidades dos algoritmos atualmente existentes e a importância crescente das modelagens grafo-sanduíche para inúmeras aplicações práticas. Este trabalho reúne a evolução das técnicas de resolução deste problema e os esforços do autor no sentido de solucioná-lo eficientemente, culminando na correção do limite superior ate então aceito para sua complexidade temporal.
The concept of homogeneous sets has proved itself useful for the construction of graph decomposition procedures. Sandwich graphs are obtained from two pre-defined graphs that provide them with both mandatory and optional edges. In the Homogeneous Set Sandwich Problem (HSSP), one wants to find out whether there exists an instance of a sandwich graph, for a given pair of graphs, which contains some homogeneous set. Notwithstanding the existence of linear-time algorithms for solving the problem of finding homogeneous sets in a single graph, the HSSP still remains a subject for research, not only because of the rather high time complexities of current algorithms but also motivated by the increasing importance of sandwich-graph modelling to many practical applications. This thesis presents the development of techniques for solving this problem, as well as the author's efforts to find a more efficient solution to it, which culminate in the correction of the established upper bounds for its time complexity.