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:
“The Bostonians are really, as a race, far inferior in point of anything beyond mere intellect to any other set upon the continent of North America. They are decidedly the most servile imitators of the English it is possible to conceive.”
—Edgar Allan Poe (1809–1845)