In the mathematical discipline of graph theory, a feedback vertex set of a graph is a set of vertices whose removal leaves a graph without cycles. In other words, each feedback vertex set contains at least one vertex of any cycle in the graph. The feedback vertex set problem is an NP-complete problem in computational complexity theory. It was among the first problems shown to be NP-complete. It has wide applications in operating systems, database systems, genome assembly, and VLSI chip design.
Read more about Feedback Vertex Set: Definition, NP-hardness, Exact Algorithms, Approximation, Bounds, Applications
Famous quotes containing the word set:
“In America every woman has her set of girl-friends; some are cousins, the rest are gained at school. These form a permanent committee who sit on each other’s affairs, who “come out” together, marry and divorce together, and who end as those groups of bustling, heartless well-informed club-women who govern society. Against them the Couple of Ehepaar is helpless and Man in their eyes but a biological interlude.”
—Cyril Connolly (1903–1974)