• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Frontiers in algorithmics and algorithmic aspects in information and management >Two Hardness Results on Feedback Vertex Sets
【24h】

Two Hardness Results on Feedback Vertex Sets

机译：反馈顶点集的两个硬度结果

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

摘要

A feedback vertex set is a subset of vertices whose deletion makes the remaining graph a forest. We show that the minimum FVS (MFVS) in star convex bipartite graphs is NP-hard to find, and give a tighter lower bound on the size of MFVS in sparse random graphs, to provide further evidence on the hardness of random CSPs.
机译：反馈顶点集是顶点的子集，其删除使其余图成为森林。我们表明，星形凸二分图中的最小FVS（MFVS）很难找到NP，并且在稀疏随机图中的MFVS大小上给出了更严格的下限，从而为随机CSP的硬度提供了进一步的证据。

著录项

  • 来源
  • 会议地点 Jinhua(CN);Jinhua(CN);Jinhua(CN)
  • 作者

    Wei Jiang; Tian Liu; Tienan Ren; Ke Xu;

  • 作者单位

    Key Laboratory of High Confidence Software Technologies, Ministry of Education, Institute of Software, School of Electronic Engineering and Computer Science, Peking University, Beijing 100871, China;

    Key Laboratory of High Confidence Software Technologies, Ministry of Education, Institute of Software, School of Electronic Engineering and Computer Science, Peking University, Beijing 100871, China;

    Key Laboratory of High Confidence Software Technologies, Ministry of Education, Institute of Software, School of Electronic Engineering and Computer Science, Peking University, Beijing 100871, China;

    National Lab of Software Development Environment, School of Computers, Beihang University, Beijing 100083, China;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 信息处理（信息加工）;
  • 关键词

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号