专栏首页算法和应用线性时间中的平面不相交路径
原创

线性时间中的平面不相交路径

作者:Petr A. Golovach,Stavros G. Kolliopoulos,Giannos Stamoulis,Dimitrios M. Thilikos

摘要:不想交路径问题提出在 graphGcan 中固定数量的终端对是否能通过成对不相交路径链接。在这个问题的背景下,Robertson和Seymour引入无关顶点技术,该技术从此成为图算法的标准。该技术包括检测一个顶点,该顶点在其删除创建问题的等效实例的意义上是不相关的。这样,可以解决O(n2)步骤中的问题,因为不相关顶点的检测花费O(n)时间并且可能需要移除最多的时间。在本文中,我们研究了平面不相交路径问题,其中输入图是平面的。我们引入了无关顶点技术的扩展,其中所有不相关的顶点被同时移除,使得平面不相交路径问题的实例可以以线性步数转换为具有有界树宽度的等效顶点。因此,对于每个固定数量的终端,可以在线性时间内解决平面不相交路径问题。

原文标题:Planar Disjoint Paths in Linear Time

原文摘要:The Disjoint Paths problem asks whether a fixed number of pairs of terminals in a graphGcan be linked by pairwise disjoint paths. In the context of this problem, Robertson and Seymour introduced the celebrated irrelevant vertex technique that has since become standard in graph algorithms. The technique consists of detecting a vertex that is irrelevant in the sense that its removal creates an equivalent instance of the problem. That way, one may solve the problem inO(n2)steps, as the detection of an irrelevant vertex takesO(n)time and at mostnvertices may need to be removed. In this paper we study the Planar Disjoint Paths problem where the input graph is planar. We introduce an extension of the irrelevant vertex technique where all the irrelevant vertices are removed simultaneously so that an instance of the Planar Disjoint Paths problem can be transformed in a linear number of steps to an equivalent one that has bounded treewidth. As a consequence, the Planar Disjoint Paths problem can be solved in linear time for every fixed number of terminals.

地址:https://arxiv.org/abs/1907.05940

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 时间衰减流的改进算法

    作者:Vladimir Braverman,Harry Lang,Enayat Ullah,Samson Zhou

    罗大琦
  • 论婚姻问题的泛化概括

    摘要:我们将Hall著名的婚姻定理的婚姻问题概括为我们称之为对称婚姻问题,这个问题可以被认为是最大加权二元匹配的一个特例。 我们证明了对称婚姻问题的解决方案,当...

    罗大琦
  • Googol的双面博弈与基于样本的先知不等式

    作者:José Correa,Andrés Cristi,Boris Epstein,José A. Soto

    罗大琦
  • Learning to Remember More with Less Memorization

    (Submitted on 5 Jan 2019 (v1), last revised 20 Mar 2019 (this version, v2))

    用户1908973
  • 符号网络中形成的团队(CS SI)

    在社交网络中,团队形成的问题需要一组人,他们不仅具备完成任务所需的技能,而且还能有效地相互沟通。现有的工作假设社交网络中的所有链接都是正的,也就是说,它们表示个...

    用户6853689
  • Codeforces Round #622 (Div. 2) 1313 B Different Rules

    Nikolay has only recently started in competitive programming, but already qualif...

    风骨散人Chiam
  • matplotlib quiver箭图绘制案例

    quiver绘制表示梯度变化非常有用,下面是学习过程中给出的两个例子,可以很好理解quiver的用法

    砸漏
  • 利用人工智能的监控和响应系统协助东南亚医院应对COVID-19(CS)

    为了解医疗机构的现状,本研究提出了一种用于监测和响应COVID-19的系统,该系统可以帮助东南亚的国家明确激增的患者数目和呼吸机等重要设备的短缺情况。同时,该系...

    Pamela_Lin
  • win10 uwp xaml 绑定接口

    早上快乐 就在你的心问了我一个问题,他使用的属性是显式继承,但是无法在xaml绑定

    林德熙
  • 深度单图像处理(CS)

    多年来,由于这项任务的受欢迎程度和商业重要性,图像处理吸引了许多研究。已有许多基于深度神经网络的方法用于许多图像处理任务。深度方法的主要问题是需要训练来自与目标...

    DDDDDaemon

扫码关注云+社区

领取腾讯云代金券