O Problema do Caminho Positivo Mínimo - Albuquerque, Felipe; Campêlo, Manoel; Figueiredo, Tatiane (Anais do Encontro de Teoria da Computação (ETC); 2023: Anais do VIII Encontro de Teoria da Computação, 2023)
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.