Feedback Arc Set

GPTKB entity

Statements (19)
Predicate Object
gptkbp:instanceOf theoretical computer science
gptkbp:alsoKnownAs gptkb:FAS
gptkbp:application gptkb:list
circuit design
data flow analysis
gptkbp:complexity gptkb:NP-hard
gptkbp:defines A set of edges whose removal makes a directed graph acyclic
gptkbp:estimatedCost yes
gptkbp:field computer science
graph theory
gptkbp:firstDescribed 1970s
https://www.w3.org/2000/01/rdf-schema#label Feedback Arc Set
gptkbp:minimumFeedbackArcSet smallest set of edges whose removal makes the graph acyclic
gptkbp:relatedTo gptkb:Feedback_Vertex_Set
graph
cycle
gptkbp:bfsParent gptkb:Karp's_21_NP-complete_problems
gptkb:Reducibility_Among_Combinatorial_Problems_(Karp,_1972)
gptkbp:bfsLayer 6