Sobre Ordens e Grafos de Intervalo
Autores
|
4986 |
410,6,1887
|
|
|
4987 |
410,6,1887
|
|
|
4988 |
410,6,1887
|
Informações:
Publicações do PESC
Esta tese tem como foco o estudo de algumas propriedades estruturais de grafos de intervalo e ordens de intervalo e acerca da complexidade em reconhecer tais propriedades. Em particular, apresentamos os seguintes resultados: (i) fornecemos caracterizações de cliques extremas e grafos representáveis por cliques homogêneas; (ii) introduzimos uma nova dimensão de ordens chamada dimensão linear-intervalar, mostrando sua conexão com o problema de reconhecimento de grafos PI. Mostramos que a dimensão linear-intervalar é um invariante de comparabilidade e descrevemos uma caracterização para grafos PI em termos desta dimensão. Fornecemos exemplos de ordens possuindo dimensão linear-intervalar arbitrária; (iii) provemos o estado-da-arte do problema de contagem de intervalos, apresentando os resultados existentes na literatura à respeito; e (iv) fornecemos algoritmos eficientes para a computação da contagem de intervalos de generalizações de grafos de limiar, além de apresentar outras propriedades relacionadas à contagem de intervalos de grafos e ordens.
This thesis has as focus the study of some structural properties of interval graphs and interval orders and the complexity aspect of recognizing such properties. In particular, we present the following results: (i) we provide characterizations of extreme cliques and homogeneously-clique representable graphs; (ii) we introduce a new order dimension named linear-interval dimension, showing the close existing relation to the recognition problem of PI graphs. We show that the linear-interval dimension is a comparability invariant and we describe a characterization of PI graphs in terms of such a concept. We provide examples of orders having arbitrarily large linear-interval dimension values; (iii) we provide the state-of-the-art knowledge about the interval count problem, by presenting the known results in literature regarding this subject; and (iv) we provide efficient algorithms for the computation of the interval count of generalizations of threshold graphs, besides presenting other properties related to the interval count of graphs and orders.