专栏首页arxiv.org翻译专栏关于在时间分割和排列图中寻找分隔符的问题(CS)

关于在时间分割和排列图中寻找分隔符的问题(CS)

通过移除最小数量的顶点来移除图中两个顶点s和z之间的所有连接是算法图论中的一个基本问题。这个(s,z)分离问题是众所周知的多项式可解的,在许多与网络连通性相关的应用中是一个重要的原语。我们研究了时间图的NP-hard时序(s,z)分离问题,时间图是指具有固定顶点集但边集在离散时间步长上发生变化的图。为了解决这个问题,我们将层(例如,在特定时间点以边为特征的图)限制在特定的图类中。我们将时间图的层限制为所有分裂图或所有排列图(都是完美的图类),并提供了既难处理又易于处理的结果。特别地,我们展示了在时间分割和时间排列图上,这个问题在一般情况下仍然是np困难的,但我们也发现了有希望的固定参数可溯源岛,特别是基于测量“随时间变化”的参数化。

原文题目:On Finding Separators in Temporal Split and Permutation Graphs

原文:Removing all connections between two vertices s and z in a graph by removing a minimum number of vertices is a fundamental problem in algorithmic graph theory. This (s,z)-separation problem is well-known to be polynomial solvable and serves as an important primitive in many applications related to network connectivity. We study the NP-hard temporal (s,z)-separation problem on temporal graphs, which are graphs with fixed vertex sets but edge sets that change over discrete time steps. We tackle this problem by restricting the layers (i.e., graphs characterized by edges that are present at a certain point in time) to specific graph classes. We restrict the layers of the temporal graphs to be either all split graphs or all permutation graphs (both being perfect graph classes) and provide both intractability and tractability results. In particular, we show that in general the problem remains NP-hard both on temporal split and temporal permutation graphs, but we also spot promising islands of fixed-parameter tractability particularly based on parameterizations that measure the amount of "change over time".

原文链接:https://arxiv.org/abs/2105.12003

原文作者:Nicolas Maack, Hendrik Molter, Rolf Niedermeier, Malte Renken

我来说两句

0 条评论
登录 后参与评论

相关文章

  • python 实现在无序数组中找到中位数方法

    1、求一个无序数组的中位数, (若数组是偶数,则中位数是指中间两个数字之和除以2,若数组是奇数,则中位数是指最中间位置。要求:不能使用排序,时间复杂度尽量低

    砸漏
  • 14. 切割图像 - 智能剪刀(Intelligent Scissors)

    我还提到即便是像Alpha融合这类方法,也依赖于准确的抠图。那么问题来了?我们如何才能从图像中抠出想要的物体呢?

    HawkWang
  • 生物学家与计算机科学家合作的十条原则

    生物学日益数字化,科学家每天都在产生海量数据,将分子转化为序列和文本文件。作为生物学家,您可能需要帮助分析所有这些数据,并且一而再再而三的考虑与计算机科学家合作...

    生信菜鸟团
  • Shell进阶必会的几个工具,你都掌握了吗?(附真实企业面试题)

    在之前的一篇博客?《零基础小白如何入门Shell,快来看看(收藏)这篇大总结!!》中,博主已经为大家介绍了Shell常见的入门级操作,本篇博客,...

    大数据梦想家
  • 算法细节系列(22):什么时候贪心完!

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 输入/输出和管道及相关的命令

    文件描述符是Linux系统内部使用的一个文件代号、它决定从哪里读入命令所需的输入和将命令产生的输出及错误显示送到什么地方。

    狼啸风云
  • 了解搜索引擎背后的经典数据结构和算法

    我们每天都在用 Google, 百度这些搜索引擎,那大家有没想过搜索引擎是如何实现的呢,看似简单的搜索其实技术细节非常复杂,说搜索引擎是 IT 皇冠上的明珠也不...

    架构师修行之路
  • 序列比对(21)中间字符串问题的算法及实现代码

    《序列比对(20)基序发现问题的算法及实现代码》给出了基序问题的算法和实现代码。本文将介绍中间字符串问题的算法,并给出实现代码。

    一只羊
  • LeetCode动画 | 3. 无重复字符的最长子串

    今天分享一个LeetCode题,题号是3,标题是:无重复字符的最长子串,题目标签:散列表、双指针和字符串。解题思路里有算法动画视频,别漏看了哦,这是最直观最可视...

    我脱下短袖

扫码关注云+社区

领取腾讯云代金券