Convexidades em Grafos: Intermediações, Parâmetros e Conversões

• Vinicius dos Santos UFRJ
• Jayme Szwarcfiter UFRJ
• Dieter Rautenbach Universität Ulm

Resumo

Inspirados no conceito de convexidade da geometria euclideana, diversos trabalhos envolvendo convexidades abstratas vêm sendo feitos recentemente. Nesta tese consideramos o caso particular de convexidades em grafos, o qual pode ser utilizado para modelar diversas aplicações, como influência em redes sociais, sistemas distribuídos e automata celular, dentre outras. São abordados problemas envolvendo intermediações, o número de envoltória, o número de Radon, o número de Carathéodory e conversões com limite de tempo em grafos. Os resultados apresentados compreendem caracterizações, algoritmos eficientes para a determinação de parâmetros, provas de NPcompletude e limites superiores e inferiores.

Referências

Araújo, R., Sampaio, R. M., dos Santos, V. F., and Szwarcfiter, J. (2014). The convexity of induced paths of order three and applications: complexity aspects. Submetido ao periódico Discrete Applied Mathematics.

Barbosa, R., Rautenbach, D., dos Santos, V. F., and Szwarcfiter, J. L. (2013). On minimal and minimum hull sets. In Electronic Notes in Discrete Mathematics. Proceedings of the VII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS), volume 44, pages 207 – 212.

Dantas, S., de Figueiredo, C. M. H., Mazzuoccolo, G., Preissmann, M., dos Santos, V. F., and Sasaki, D. (2013). On total coloring and equitable total coloring of cubic graphs with large girth. In Proceedings of 12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2013), pages 79–83, Enschede.

Dourado, M. C., Rautenbach, D., dos Santos, V. F., Schäfer, P. M., and Szwarcfiter, J. L. (2013a). On the Carathéodory number of interval and graph convexities. Theoretical Computer Science, 510(0):127 – 135.

Dourado, M. C., Rautenbach, D., dos Santos, V. F., Schäfer, P. M., Szwarcfiter, J. L., and Toman, A. (2012a). On the Radon number for P3-convexity. In LATIN, volume 7256 of Lecture Notes in Computer Science, pages 267–278. Springer.

Dourado, M. C., Rautenbach, D., dos Santos, V. F., Schäfer, P. M., Szwarcfiter, J. L., and Toman, A. (2012b). An upper bound on the P3-Radon number. Discrete Mathematics, 312(16):2433 – 2437.

Dourado, M. C., Rautenbach, D., dos Santos, V. F., Schäfer, P. M., Szwarcfiter, J. L., and Toman, A. (2013b). Algorithmic and structural aspects of the P3-Radon number. Annals of Operations Research, 206(1):75–91.

Dourado, M. C., Rautenbach, D., dos Santos, V. F., and Szwarcfiter, J. L. (2012c). Characterization and recognition of Radon-independent sets in split graphs. Information Processing Letters, 112(24):948 – 952.

Habib, M., Julien, D., McConnell, R., dos Santos, V. F., and Szwarcfiter, J. L. (2014). Characterizing clique graphs of chordal comparability graphs. Aceito para publiç ˜ao no periódico Matematica Contemporanea.

Ramos, I. d. F., dos Santos, V. F., and Szwarcfiter, J. L. (2014). Complexity aspects of the computation of the rank of a graph. Submetido ao periódico Discrete Mathematics and Theoretical Computer Science.

Rautenbach, D., dos Santos, V. F., and Schäfer, P. M. (2014). Irreversible conversion processes with deadlines. Journal of Discrete Algorithms, 26:69 – 76.

Rautenbach, D., dos Santos, V. F., Schäfer, P. M., and Szwarcfiter, J. L. (2011a). Characterization and representation problems for intersection betweennesses. Discrete Applied Mathematics, 159(5):389 – 395.

Rautenbach, D., dos Santos, V. F., Schäfer, P. M., and Szwarcfiter, J. L. (2011b). On subbetweennesses of trees: Hardness, algorithms, and characterizations. Computers & Mathematics with Applications, 62(12):4674 – 4681.