O Problema do Caminho Positivo Mínimo
Resumo
Grafos de sinais são grafos onde a cada aresta/arco é associado um rótulo positivo ou negativo. Um caminho é positivo se contém um número par de arestas/arcos negativos. Apresentamos algoritmos polinomiais para encontrar um caminho positivo de peso mínimo em grafos de sinais não direcionados. Mostramos que o problema se torna NP-Difícil em digrafos de sinais, mesmo com pesos unitários.
Referências
Albuquerque, F., Campêlo, M., and Figueiredo, T. (2022). O problema de formação de equipes com caminhos mínimos compatíveis: uma abordagem exata. Anais do Simpósio Brasileiro de Pesquisa Operacional, 54(152933):2965–1476.
Cartwright, D. and Harary, F. (1956). Structural balance: a generalization of heider’s theory. Psychological Review, 63(5):277–293.
Edmonds, J. (1965a). Maximum matching and a polyhedron with 0, 1-vertices. Journal of research of the National Bureau of Standards B, 69(125-130):55–56.
Edmonds, J. (1965b). Paths, trees, and flowers. Canadian Journal of mathematics, 17:449–467.
Fortune, S., Hopcroft, J., and Wyllie, J. (1980). The directed subgraph homeomorphism problem. Theoretical Computer Science, 10(2):111–121.
Guler, B., Varan, B., Tutuncuoglu, K., Nafea, M., Zewail, A. A., Yener, A., and Octeau, D. (2014). Optimal strategies for targeted influence in signed networks. In IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASO-NAM 2014), pages 906–911.
Guler, B., Varan, B., Tutuncuoglu, K., Nafea, M., Zewail, A. A., Yener, A., and Octeau, D. (2015). Using social sensors for influence propagation in networks with positive and negative relationships. IEEE Journal of Selected Topics in Signal Processing, 9(2):360–373.
Heider, F. (1946). Attitudes and cognitive organization. The Journal of psychology, 21(1):107–112.
Kouvatis, I., Semertzidis, K., Zerva, M., Pitoura, E., and Tsaparas, P. (2020). Forming compatible teams in signed networks. In Proceedings of the 23rd International Conference on Extending Database Technology (EDBT), pages 363–366. OpenProceedings.org.
Lapaugh, A. S. and Papadimitriou, C. H. (1984). The even-path problem for graphs and digraphs. Networks, 14(4):507–513.
Cartwright, D. and Harary, F. (1956). Structural balance: a generalization of heider’s theory. Psychological Review, 63(5):277–293.
Edmonds, J. (1965a). Maximum matching and a polyhedron with 0, 1-vertices. Journal of research of the National Bureau of Standards B, 69(125-130):55–56.
Edmonds, J. (1965b). Paths, trees, and flowers. Canadian Journal of mathematics, 17:449–467.
Fortune, S., Hopcroft, J., and Wyllie, J. (1980). The directed subgraph homeomorphism problem. Theoretical Computer Science, 10(2):111–121.
Guler, B., Varan, B., Tutuncuoglu, K., Nafea, M., Zewail, A. A., Yener, A., and Octeau, D. (2014). Optimal strategies for targeted influence in signed networks. In IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASO-NAM 2014), pages 906–911.
Guler, B., Varan, B., Tutuncuoglu, K., Nafea, M., Zewail, A. A., Yener, A., and Octeau, D. (2015). Using social sensors for influence propagation in networks with positive and negative relationships. IEEE Journal of Selected Topics in Signal Processing, 9(2):360–373.
Heider, F. (1946). Attitudes and cognitive organization. The Journal of psychology, 21(1):107–112.
Kouvatis, I., Semertzidis, K., Zerva, M., Pitoura, E., and Tsaparas, P. (2020). Forming compatible teams in signed networks. In Proceedings of the 23rd International Conference on Extending Database Technology (EDBT), pages 363–366. OpenProceedings.org.
Lapaugh, A. S. and Papadimitriou, C. H. (1984). The even-path problem for graphs and digraphs. Networks, 14(4):507–513.
Publicado
06/08/2023
Como Citar
ALBUQUERQUE, Felipe; CAMPÊLO, Manoel; FIGUEIREDO, Tatiane.
O Problema do Caminho Positivo Mínimo. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 8. , 2023, João Pessoa/PB.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 89-93.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2023.230579.
