An Algorithm for the Feedback Vertex Set Problem on a Normal Helly Circular-Arc GraphReport as inadecuate




An Algorithm for the Feedback Vertex Set Problem on a Normal Helly Circular-Arc Graph - Download this document for free, or read online. Document in PDF available to download.

The feedback vertex set FVS problem is tofind the set of vertices of minimum cardinality whose removal renders the graphacyclic. The FVS problem has applications in several areas such ascombinatorial circuit design, synchronous systems, computer systems, andvery-large-scale integration VLSI circuits. The FVS problem is known to beNP-hard for simple graphs, but polynomi-al-time algorithms have been found forspecial classes of graphs. The intersection graph of a collection of arcs on acircle is called a circular-arc graph. A normal Helly circular-arc graph is aproper subclass of the set of circular-arc graphs. In this paper, we present analgorithm that takes  time to solve the FVS problem in a normal Hellycircular-arc graph with n vertices and m edges.

KEYWORDS

Design and Analysis of Algorithms, Feedback Vertex Set, Normal Helly Circular-Arc Graphs, Intersection Graphs

Cite this paper

Honma, H. , Nakajima, Y. and Sasaki, A. 2016 An Algorithm for the Feedback Vertex Set Problem on a Normal Helly Circular-Arc Graph. Journal of Computer and Communications, 4, 23-31. doi: 10.4236-jcc.2016.48003.





Author: Hirotoshi Honma, Yoko Nakajima, Atsushi Sasaki

Source: http://www.scirp.org/



DOWNLOAD PDF




Related documents