Sobre Ordens e Grafos de Intervalo

• Márcia R. Cerioli UFRJ
• Fabiano de S. Oliveira UFRJ
• Jayme L. Szwarcfiter UFRJ

Resumo

A tese resumida neste trabalho tem como foco o estudo de propriedades estruturais de grafos e ordens de intervalo e a complexidade em reconhecê-las. Em particular, (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; (iii) provemos o estado-da-arte do problema de contagem de intervalos, apresentando os resultados existentes na literatura; e (iv) fornecemos algoritmos eficientes para a computação da contagem de intervalos de generalizações de grafos de limiar.

Referências

Cerioli, M. R., Oliveira, F. d. S., and Szwarcfiter, J. L. (2008). Linear-interval dimension and pi orders. Electronic Notes in Discrete Mathematics, 30:111–116.

Cerioli,M. R., Oliveira, F. d. S., and Szwarcfiter, J. L. (2010a). Extreme cliques in interval graphs. Ars Combinatoria, 94:103–114.

Cerioli,M. R., Oliveira, F. d. S., and Szwarcfiter, J. L. (2010b). On representing an interval graph using the minimum number of interval lengths. Matemática Contemporânea, 39:59–67.

Cerioli, M. R., Oliveira, F. d. S., and Szwarcfiter, J. L. (2011). On counting interval lengths of interval graphs. Discrete Applied Mathematics, 159(7):532–543.

Fishburn, P. C. (1985). Interval Orders and Interval Graphs. John Wiley & Sons.

Golumbic, M. and Trenk, A. (2003). Tolerance Graphs. Cambridge University Press.

Karp, R. M. (1993). Mapping the genome: some combinatorial problems arising in molecular biology. In STOC ’93: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, pages 278–285, New York. ACM.

Lin, Y.-L. (2002). Triangle graphs and simple trapezoid graphs. Journal of Information Science and Engineering, 18(3):467–473.

Oliveira, F. d. S. (2006). Caracterizações de grafos de interseção de triângulos. Master’s thesis, COPPE/Universidade Federal do Rio de Janeiro, Brasil.

Papadimitriou, C. H. and Yannakakis, M. (1979). Scheduling interval-ordered tasks. SIAM Journal on Computing, 8(3):405–409.

Pe’er, I. and Shamir, R. (1997). Realizing interval graphs with size and distance constraints. SIAM Journal on Discrete Mathematics, 10(4):662–687.

Roberts, F. (1976). DiscreteMathematicalModels with Applications to Social, Biological, and Environmental Problems. Prentice Hall.

Spinrad, J. P. (2003). Efficient Graph Representations, volume 19 of Fields Institute Monographs. American Mathematical Society.