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:
“1st Witch. When shall we three meet again?
In thunder, lightning, or in rain?
2nd Witch. When the hurly-burly’s done,
When the battle’s lost and won.
3rd Witch. That will be ere set of sun.
1st Witch. Where the place?
2nd Witch. Upon the heath.
3rd Witch. There to meet with Macbeth.”
—William Shakespeare (1564–1616)