Caracterizando facetas do politopo do Subgrafo Gerador Balanceado Máximo via comutação - Coelho, Natália; Campêlo, Manoel (Anais do Encontro de Teoria da Computação (ETC); 2026: Anais do XI Encontro de Teoria da Computação, 2026)
Analisamos o politopo associado a uma formulação para o problema do Subgrafo Gerador Balanceado Máximo em grafos de sinais. Demonstramos a correspondência entre facetas induzidas por um subgrafo de sinais e suas comutações (i.e., grafos obtidos pela inversão dos sinais de qualquer corte de arestas do grafo). Utilizamos dessa propriedade para demonstrar desigualdades válidas indutoras de faceta nesse politopo.