• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Computational Science and Its Applications(ICCSA 2006) pt.5; 20060508-11; Glasgow(GB) >Feedback Vertex Sets in Rotator Graphs
【24h】

Feedback Vertex Sets in Rotator Graphs

机译：旋转图中的反馈顶点集

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This paper provides an algorithm for finding feedback vertex set in rotator graphs. Feedback vertex set is a subset of a graph whose removal causes an acyclic graph and is developed in various topologies of interconnected networks. In 1992, Corbett pioneered rotator graphs, whose interesting topological structures attract many researchers to publish relative papers in recent years. In this paper, we first develops feedback vertex set algorithm for rotator graphs. Our algorithm utilizes the technique of dynamic programming and generates a feedback vertex set of size n!/3 for a rotator graph of scale n, which contains n! nodes. The generated set size is proved to be minimum. Finding a minimum feedback vertex set is a NP-hard problem for general graphs. The time complexity of our algorithm, which finds a minimum feedback vertex set for a rotator graph of scale n, is proved to be O(n~(n-3)).
机译：本文提供了一种在旋转图中寻找反馈顶点集的算法。反馈顶点集是图的子集，其删除会导致非循环图，并且在互连网络的各种拓扑中得到发展。 1992年，Corbett率先提出了转子图，其有趣的拓扑结构吸引了许多研究人员在最近几年发表相关论文。在本文中，我们首先开发了用于转子图的反馈顶点集算法。我们的算法利用动态编程技术，为尺度为n的旋转图生成了大小为n！/ 3的反馈顶点集，其中包含n！节点。证明生成的集合大小最小。对于一般图形来说，找到最小反馈顶点集是一个NP难题。我们的算法的时间复杂度是O（n〜（n-3）），它找到了比例为n的旋转图的最小反馈顶点集。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号