• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs
【24h】

Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs

机译：子集反馈顶点的多项式时间算法在间隔图和排列图上的问题

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

摘要

Given a vertex-weighted graph G = (V, E) and a set S subset of V, a subset feedback vertex set X is a set of the vertices of G such that the graph induced by V X has no cycle containing a vertex of S. The SUBSET FEEDBACK VERTEX SET problem takes as input G and S and asks for the subset feedback vertex set of minimum total weight. In contrast to the classical FEEDBACK VERTEX SET problem which is obtained from the SUBSET FEEDBACK VERTEX SET problem for S = V, restricted to graph classes the SUBSET FEEDBACK VERTEX SET problem is known to be NP-complete on split graphs and, consequently, on chordal graphs. However, whereas FEEDBACK VERTEX SET iS polynomially solvable for AT-free graphs, no such result is known for the SUBSET FEEDBACK VERTEX SET problem on any subclass of AT-free graphs. Here we give the first polynomial-time algorithms for the problem on two subclasses of AT-free graphs: interval graphs and permutation graphs. Moreover, towards the unknown complexity of the problem for AT-free graphs, we give a polynomial-time algorithm for co-bipartite graphs. Thus, we contribute to the first positive results of the SUBSET FEEDBACK VERTEX SET problem when restricted to graph classes for which FEEDBACK VERTEX SET is solved in polynomial time. (C) 2018 Elsevier B.V. All rights reserved.
机译：给定顶点加权图G =（V，e）和V的集合S子集，子集反馈顶点组X是G的一组G，使得由V x引起的图形没有包含顶点的循环S.子集反馈顶点设置问题作为输入G和S，并要求最小总重量的子集反馈顶点集。与从子集反馈顶点的典型反馈顶点设置问题与s = v获得的典型反馈顶点设置问题相比，仅仅是图形类，已知子集反馈顶点设置问题是在拆分图上为np完成，并且因此在chordal上图表。然而，而反馈顶点组是针对无目标曲线图的多项值可解决的，但是在不可自由图形的任何子类上，不知道这些结果。在这里，我们为第一个多项式时间算法提供了一个关于无目标图形的两个子类的问题：区间图和排列图。此外，朝着无目标图的问题的未知复杂性，我们提供了一种用于共同二分图的多项式算法。因此，当限于在多项式时间中求出反馈顶点组的图形类时，我们有助于子集反馈顶点设定问题的第一个正结果。 （c）2018 Elsevier B.v.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号