Geração e Enumeração de Extensões Lineares em Conjuntos Parcialmente Ordenados

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.