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

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

Abstract

Motivated by the concept of convexity, from Euclidean geometry, much work has been done on abstract convexities recently. In this thesis, the particular case of graph convexity is considered, which can be used to model many applications, such as influence on social networks, distributed systems and cellular automata, among others. We address problems involving betweenesses, the hull number, the Radon number, the Carathéodory number and conversions with deadlines in graphs. The results shown in this thesis include characterizations, efficient algorithms for determining parameters, NP-completeness proofs, and upper and lower bounds.

References

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.