ENLACES DAS CONVEXIDADES DE CAMINHOS CURTOS EM PROBLEMAS DE PARTIÇÕES E SEPARAÇÕES CONVEXAS

ENLACES DAS CONVEXIDADES DE CAMINHOS CURTOS EM PROBLEMAS DE PARTIÇÕES E SEPARAÇÕES CONVEXAS

Castro, Lorrana F. de; Oliveira, Rodolfo A. de; Protti, Fábio

Artigo Completo:

Neste trabalho apresentamos alguns resultados teórico-computacionais sobre a convexidade P3 e a convexidade P 3* nas perspectivas de partição e separação convexas. Na vertente teórica, mostramos sobre quais aspectos ambas as convexidades são equivalentes, identicamos os menores grafos que não admitem uma partição convexa e listamos infinitos grafos com tal característica e, por último, analisamos os moldes de uma separação para caminhos, árvores, ciclos e cliques. Na vertente computacional, mostramos a NP-completude do problema de partição convexa em ambas as convexidades, mesmo restrito a classes particulares de grafos.

Neste trabalho apresentamos alguns resultados teórico-computacionais sobre a convexidade P3 e a convexidade P 3* nas perspectivas de partição e separação convexas. Na vertente teórica, mostramos sobre quais aspectos ambas as convexidades são equivalentes, identicamos os menores grafos que não admitem uma partição convexa e listamos infinitos grafos com tal característica e, por último, analisamos os moldes de uma separação para caminhos, árvores, ciclos e cliques. Na vertente computacional, mostramos a NP-completude do problema de partição convexa em ambas as convexidades, mesmo restrito a classes particulares de grafos.

Palavras-chave:

DOI: 10.5151/spolm2019-090

Referências bibliográficas

• [1] BERGER, M. Convexity. Amer. Math. Monthly, v. 97, n. 8, p. 650 { 678, 1990. 2 [2] VAN DE VEL, M. L. J. Theory of Convex Structures. 1st edition. ed. Amsterdam: North Holland, 1993. 2, 11 [3] MOSCARINI, M.; MALVESTUTO, F. M. Two classes of graphs in which some problems related to convexity are eciently solvable. Discrete Mathematics, Algorithms and Applications, v. 10, n. 03, p. 1850042, 2018. 2 [4] MATHEW, J. K.; MATHEW, S. Monophonic convexity in weighted graphs. Discrete Mathematics, Algorithms and Applications, v. 10, n. 01, p. 1850010, 2018. 2 [5] MARCILON, T.; SAMPAIO, R. The maximum infection time of the p3 convexity in graphs with bounded maximum degree. Discrete Applied Mathematics, v. 251, p. 245 { 257, 2018. 2 [6] MORDESON, J. N.; MATHEW, S. Distances and convexity in fuzzy graphs. In: . Advanced Topics in Fuzzy Graph Theory. Cham: Springer International Publishing, 2019. p. 93{126. 2 [7] COELHO, E. M. et al. On the p3-hull number of some products of graphs. Discrete Applied Mathematics, v. 253, p. 2 { 13, 2019. 14th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2016). 2 [8] HARARY, F.; NIEMINEN, J. Convexity in graphs. J. Dierential Geom, v. 16, n. 2, p. 185{190, 1981. 3 [9] FARBER, M.; JAMISON, R. E. Convexity in graphs and hypergraphs. SIAM Journal on Algebraic Discrete Methods, v. 7, n. 3, p. 433{444, 1986. 3 [10] DUCHET, P. Convex sets in graphs, ii. minimal path convexity. Journal of Combinatorial Theory, Series B, v. 44, n. 3, p. 307 { 316, 1988. 3 [11] CHANGAT, M.; MATHEW, J. On triangle path convexity in graphs. Discrete Mathematics, v. 206, p. 91 { 95, 1999. 3 [12] CaCERES, J.; MaRQUEZ, A.; PUERTAS, M. L. Steiner distance and convexity in graphs. European Journal of Combinatorics, v. 29, n. 3, p. 726 { 736, 2008. 3 [13] PELAYO, I. M. Geodesic Convexity in Graphs. 1st edition. ed. New York: Springer, 2013. 3 [14] PENSO, L. D. et al. Complexity analysis of p3-convexity problems on boundeddegree and planar graphs. Theoretical Computer Science, v. 607, p. 83 { 95, 2015. [15] CENTENO, C. C.; DOURADO, M. C.; SZWARCFITER, J. L. On the convexity of paths of length two in undirected graphs. Electronic Notes in Discrete Mathematics, v. 32, p. 11 { 18, 2009. DIMAP Workshop on Algorithmic Graph Theory. 3 [16] ARAuJO, R. T.; SAMPAIO, R. M.; SZWARCFITER, J. L. The convexity of induced paths of order three. Electronic Notes in Discrete Mathematics, v. 44, p. 109 { 114, 2013. 3 [17] GIMBEL, J. Some remarks on the convexity number of a graph. Graphs and Combinatorics, v. 19, n. 3, p. 357{361, 2003. 3 [18] DOURADO, M. C.; PROTTI, F.; SZWARCFITER, J. L. Complexity results related to monophonic convexity. Discrete Applied Mathematics, v. 158, n. 12, p. 1268 { 1274, 2010. 3 [19] ARTIGAS, D. et al. Partitioning a graph into convex sets. Discrete Mathematics, v. 311, n. 17, p. 1968 { 1977, 2011. 3 [20] CENTENO, C. C. et al. Convex partitions of graphs induced by paths of order three. Discrete Mathematics & Theoretical Computer Science, v. 12, n. 5, p. 175{ 184, 2010. 3, 12 [21] BONDY, A.; MURTY, M. R. Graph theory. 1st edition. ed. London: Springer, 2008. 5 [22] CHVATAL, V. Recognizing decomposable graphs. Journal of Graph Theory, v. 8, n. 1, p. 51{53, 1984. 12 [23] PATRIGNANI, M.; PIZZONIA, M. The complexity of the matching-cut problem. In: BRANDSTADT, A.; LE, V. B. (Ed.). Graph-Theoretic Concepts in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001. p. 284{ 295. 12 [24] BONSMA, P. The complexity of the matching-cut problem for various graph classes. Electronic Notes in Discrete Mathematics, v. 13, p. 18 { 21, 2003. 12, 14 [25] HOANG-OANH LE; BANG LE, V. On the Complexity of Matching Cut in Graphs of Fixed Diameter. In: HONG, S.-H. (Ed.). 27th International Symposium on Algorithms and Computation (ISAAC 2016). Dagstuhl, Germany: Schloss Dagstuhl{Leibniz-Zentrum fuer Informatik, 2016. (Leibniz International Proceedings in Informatics (LIPIcs), v. 64), p. 50:1{50:12. 12 [26] BANG LE, V.; RANDERATH, B. On stable cutsets in line graphs. Theoretical Computer Science, v. 301, n. 1, p. 463 { 475, 2003. 14

Como citar:

Castro, Lorrana F. de; Oliveira, Rodolfo A. de; Protti, Fábio; "ENLACES DAS CONVEXIDADES DE CAMINHOS CURTOS EM PROBLEMAS DE PARTIÇÕES E SEPARAÇÕES CONVEXAS", p-1219-1234. In: Anais do XIX Simpósio de Pesquisa Operacional & Logística da Marinha. São Paulo: Blucher, 2020.
ISSN 21756295, DOI 10.5151/spolm2019-090