Alguns Problemas Algorítmicos em Conjuntos Parcialmente Ordenados e o Teorema de Dilworth
Authors:
Autores
Person role | Person | |
---|---|---|
3679 |
6,27
|
|
3678 |
6,27
|
Informations:
Pesc publication
Neste trabalho se determina a complexidade de problemas algorítmicos formulados sobre grafos relacionados a conjuntos parcialmente ordenados; além de um algoritmo para caracterização unívoca de conjuntos parcialmente ordenados, se determinam como de natureza polinomial ou NP-completos alguns problemas de obtenção de grafos orientados em que o número de Dilworth é minimo ou máximo. Adicionalmente são obtidos alguns resultados para problemas sobre grafos de comparabilidade e na determinação do Kernel de um dígrafo.