On the complexity of feedback set problems in signed digraphs

Marco Montalva, Julio Aracena, Anahí Gajardo

Resultado de la investigación: Contribución a una revistaArtículorevisión exhaustiva

10 Citas (Scopus)

Resumen

Given a directed graph G = (V, E) and w : E → {- 1, + 1} a sign function on the arcs of G, we study the positive feedback vertex set problem (PFVS) which consists on finding a minimum cardinality set of vertices that meets all the cycles with an even number of negative arcs. This problem is closely related with the number of steady states of Regulatory Boolean Networks. We also study the negative feedback vertex set problem which consists on finding a minimum cardinality set of vertices that meets all the cycles with an odd number of negative arcs, and the analogous problems for arc sets. We prove that all of these problems are NP-complete.

Idioma originalInglés
Páginas (desde-hasta)249-254
Número de páginas6
PublicaciónElectronic Notes in Discrete Mathematics
Volumen30
N.ºC
DOI
EstadoPublicada - 20 feb. 2008

Huella

Profundice en los temas de investigación de 'On the complexity of feedback set problems in signed digraphs'. En conjunto forman una huella única.

Citar esto