Propriedades do Problema da Floresta Geradora k-Rotulada

Autor:	Manoel B. Campêlo, Pedro Jorge De Abreu Figueredo
Rok vydání:	2020
Zdroj:	Anais do Encontro de Teoria da Computação (ETC 2020).
Popis:	Consideramos o problema da Floresta Geradora k-Rotulada, que consiste em encontrar uma floresta geradora de um grafo colorido em arestas com a menor quantidade de árvores e no máximo k cores. Derivamos duas caracterizações para o problema e mostramos estratégias para converter uma instância em outra equivalente. Esses resultados impactam o desenvolvimento de abordagens de solução. Identificamos também alguns casos polinomiais.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::39456ea34a15eee63a9fd55d6f1fe9cd https://doi.org/10.5753/etc.2020.11092 Zobrazit plný text záznamu