Geração e Enumeração de Extensões Lineares em Conjuntos Parcialmente Ordenados
Autores
3265 |
Andréa Werneck Richa
|
6,1482
|
3266 |
6,1482
|
Informações:
Publicações do PESC
Este trabalho se concentra na análise dos problemas de geração e enumeração de extensões lineares de conjuntos parcialmente ordenados (posets), ambos fortemente relacionados entre si. O primeiro trata da questão de se gerar (listas) efetivamente todas as extensões lineares de um poset. Este problema foi resolvido de maneira ótima (em tempo médio constante) para o caso geral, mas continua em aberto quando exigimos que cada duas extensões lineares listadas sucessivamente difiram entre si por uma transposição, ou quando exigimos que esta geração seja feita em ordem lexicográfica. Algumas subclasses de posets que admitem uma geração por transposição são caracterizadas e um algoritmo de tempo médio constante é descrito para a classe dos posets graduados. O problema da geração em ordem lexicográfica para posets série-paralelos é resolvido de maneira ótima. Um teorema original mostra que todo poset admite uma geração por inserção para a esquerda e uma por inserção para a direita. O problema de enumeração, recentemente provado sei # P-complet o no caso geral, simplesmente conta as extensões lineares de um dado poset. Esta tese discute ainda alguns algoritmos (não-polinomiais) para o caso geral, assim como algumas subclasses de posets onde o problema de enumeração foi resolvido em tempo polinomial.
This work is mainly concerned with the problems of generating and enumerating linear extensions of partially ordered sets (posets), which are strongly related to each other. The former deals with the question of effectively generating (listing) a11 the Linear extensions of a poset. An optimum solution was found for the general case (in constant average time). However it remains an open problem if it is demanded that each two successive linear extensions in the generation differ by a single transposition, or if the generation is demanded to be in lexicographical order. Some subclasses of posets that have a generation by transposition are characterized. A constant average time algorithm for the ranked posets is then given. The lexicographical order generation is solved in an optimum way for sesies-parallel posets. A new theorem is presented and it states that evesy poset has at least one generation by left insertion and at least one by right insertion. The enumeration problem, which has been recently proved to be #P-complete in general, counts a11 the linear extensions of a certain poset. This thesis also discusses some (non-polynomial) algorithms for the general case, as well as some subclasses for which this problem was solved in polynomial time.