Conjunto de arcos de realimentação sob restrições de forçamento é FPT
| Autor: | Leonardo C. de Abreu, Ana Karolinna Maia, Manoel Campêlo |
|---|---|
| Rok vydání: | 2021 |
| Zdroj: | Anais do VI Encontro de Teoria da Computação (ETC 2021). |
| DOI: | 10.5753/etc.2021.16373 |
| Popis: | O problema do conjunto de arcos de realimentação (FAS) consiste em encontrar um subconjunto de arcos de tamanho mínimo que contenha ao menos um elemento de cada circuito direcionado de um grafo direcionado. Estudamos o problema FAS sujeito a restrições de forçamento, as quais determinam que ao menos um elemento de certos pares de arcos deve estar presente em uma solução viável. Sabe-se que o problema de arcos de realimentação é FPT. Mostramos que o problema com restrições de forçamento também é FPT quando parametrizado pelo tamanho da solução. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|