We introduce a novel framework of graph modifications specific to interval graphs. We study interdiction problems with respect to these graph modifications. Given a list of original intervals, each interval has a replacement interval such that either the replacement contains the original, or the original contains the replacement. The interdictor is allowed to replace up to $k$ original intervals with their replacements. Using this framework we also study the contrary of interdiction problems which we call assistance problems. We study these problems for the independence number, the clique number, shortest paths, and the scattering number. We obtain polynomial time algorithms for most of the studied problems. Via easy reductions, it follows that on interval graphs, the most vital nodes problem with respect to shortest path, independence number and Hamiltonicity can be solved in polynomial time.


翻译:我们引入了一个针对间距图的新的图形修改框架。 我们研究与这些图形修改有关的阻截问题。 根据原始间隔列表, 每个间距有一个替换间隔, 替换的间隔要么包含原始间隔, 要么包含原始间隔。 允许截击器用替换的间隔来替换最高为原间隔美元。 我们还利用这个框架研究与我们称之为援助问题的阻截问题相反的阻截问题。 我们研究这些问题, 包括独立编号、 分类编号、 最短路径和散射号。 我们为大多数研究过的问题获得了多元时间算法 。 很容易的缩短, 在间隔图上, 最关键的节点问题就是最短的路径、 独立号 和 密尔密尔顿度 问题可以在多元时间解决 。

0
下载
关闭预览

相关内容

专知会员服务
85+阅读 · 2021年6月30日
专知会员服务
29+阅读 · 2021年4月5日
知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
106+阅读 · 2020年6月10日
【边缘智能综述论文】A Survey on Edge Intelligence
专知会员服务
120+阅读 · 2020年3月30日
专知会员服务
53+阅读 · 2020年3月16日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
已删除
将门创投
4+阅读 · 2020年6月12日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
LibRec 精选:CCF TPCI 的推荐系统专刊征稿
LibRec智能推荐
4+阅读 · 2019年1月12日
人工智能 | SCI期刊专刊信息3条
Call4Papers
5+阅读 · 2019年1月10日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
CCF B类期刊IPM专刊截稿信息1条
Call4Papers
3+阅读 · 2018年10月11日
计算机类 | 期刊专刊截稿信息9条
Call4Papers
4+阅读 · 2018年1月26日
人工智能 | 国际会议截稿信息5条
Call4Papers
6+阅读 · 2017年11月22日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Arxiv
0+阅读 · 2021年9月30日
Arxiv
0+阅读 · 2021年9月29日
VIP会员
相关资讯
已删除
将门创投
4+阅读 · 2020年6月12日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
LibRec 精选:CCF TPCI 的推荐系统专刊征稿
LibRec智能推荐
4+阅读 · 2019年1月12日
人工智能 | SCI期刊专刊信息3条
Call4Papers
5+阅读 · 2019年1月10日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
CCF B类期刊IPM专刊截稿信息1条
Call4Papers
3+阅读 · 2018年10月11日
计算机类 | 期刊专刊截稿信息9条
Call4Papers
4+阅读 · 2018年1月26日
人工智能 | 国际会议截稿信息5条
Call4Papers
6+阅读 · 2017年11月22日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Top
微信扫码咨询专知VIP会员