On the complexity of feedback set problems in signed digraphs

DOI10.1016/j.endm.2008.01.043zbMath1341.05112OpenAlexW2016743899MaRDI QIDQ3503560

Julio Aracena, Anahí Gajardo, Marco Montalva

Publication date: 5 June 2008

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2008.01.043

zbMATH Keywords

NP-completenesssigned digraphfeedback set problemsregulatory Boolean networks

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20) Signed and weighted graphs (05C22)

Related Items (4)

Complexity of fixed point counting problems in Boolean networks ⋮ Negative (and positive) circles in signed graphs: a problem collection ⋮ Maximum number of fixed points in regulatory Boolean networks ⋮ Backdoors to tractable answer set programming

Cites Work

• Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
• Maximum number of fixed points in regulatory Boolean networks
• Permanents, Pfaffian orientations, and even directed circuits
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity of feedback set problems in signed digraphs