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:
“What is love itself,
Even though it be the lightest of light love,
But dreams that hurry from beyond the world
To make low laughter more than meat and drink,
Though it but set us sighing?”
—William Butler Yeats (1865–1939)