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:
“I set it down as a fact that if all men knew what each said of the other, there would not be four friends in the world.”
—Blaise Pascal (1623–1662)