Even initial feedback vertex set problem is NP-complete

DOI10.1016/0020-0190(79)90144-3zbMath0405.68045OpenAlexW2086523902MaRDI QIDQ1257339

Dan A. Simovici, Gheorghe Grigoras

Publication date: 1979

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(79)90144-3

zbMATH Keywords

CycleDigraphFinite AutomataNp-CompletenessInitial Feedback Vertex Set Problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Unnamed Item
• On the Computational Complexity of Combinatorial Problems
• The complexity of theorem-proving procedures

This page was built for publication: Even initial feedback vertex set problem is NP-complete