An Algorithm for the Feedback Vertex Set Problem on a Normal Helly Circular-Arc Graph
2016
The feedback vertex set (FVS) problem is to
find the set of vertices of minimum cardinality whose removal renders the graph
acyclic. The FVS problem has applications in several areas such as
combinatorial circuit design, synchronous systems, computer systems, and
very-large-scale integration (VLSI) circuits. The FVS problem is known to be
NP-hard for simple graphs, but polynomi-al-time algorithms have been found for
special classes of graphs. The intersection graph of a collection of arcs on a
circle is called a circular-arc graph. A normal Helly circular-arc graph is a
proper subclass of the set of circular-arc graphs. In this paper, we present an
algorithm that takes time to solve the FVS problem in a normal Helly
circular-arc graph with n vertices and m edges.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
28
References
3
Citations
NaN
KQI