首页    期刊浏览 2024年11月08日 星期五
登录注册

文章基本信息

  • 标题:An Algorithm for the Feedback Vertex Set Problem on a Normal Helly Circular-Arc Graph
  • 本地全文:下载
  • 作者:Hirotoshi Honma ; Yoko Nakajima ; Atsushi Sasaki
  • 期刊名称:Journal of Computer and Communications
  • 印刷版ISSN:2327-5219
  • 电子版ISSN:2327-5227
  • 出版年度:2016
  • 卷号:04
  • 期号:08
  • 页码:23-31
  • DOI:10.4236/jcc.2016.48003
  • 语种:English
  • 出版社:Scientific Research Publishing
  • 摘要: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.
  • 关键词:Design and Analysis of Algorithms;Feedback Vertex Set;Normal Helly Circular-Arc Graphs;Intersection Graphs
国家哲学社会科学文献中心版权所有