Sep, 2009

连通反馈顶点集问题的 FPT 算法

PDF
TL;DR研究了连接反馈顶点集（Connected Feedback Vertex Set）问题的参数化算法，论述了该问题在图论领域的应用，证明了在普通图上复杂度为 O (2^O (k) n^O (1))，在不包含固定图 H 的图上复杂度为 O (2^O (√k logk) n^O (1))，此外将 Group Steiner Tree 问题用作子程序，并认为其独立于其他算法，具有重要意义。
connected feedback vertex setparameterized algorithmsgraphsgroup steiner treeconnectivity problems
发现论文，激发创造
  • 反馈顶点集的参数化算法的实验评估

    本文提供了关于 Feedback Vertex Set 的固定参数和分支算法的详尽实验评估。

    Mar, 2018

  • 多样化打击集的 FPT 算法

    本研究通过寻找不同的集合解决方案来解决 $d$-Hitting Set 和 Feedback Vertex Set 问题，其中集合的大小不超过 $k$，最近被引入到参数化复杂性领域。通过使用网络流公式计算最大差异集合，该算法成为了解决该问题的关键。

    Nov, 2019

  • 学习具有观测或潜在 FVS 的高斯图模型

    本文研究带有小反馈顶点集的高斯图模型，提出了有效的结构学习算法，特别是针对隐藏变量的情况，能够通过交替低秩校正等方式成功地学习模型参数，并用合成数据和真实数据进行了验证。

    Nov, 2013

  • 可预测顶点故障的连接预言机

    给定一个图，通过预测失败的顶点集合，在预处理时间和查询时间上提供条件优化的数据结构。

    Dec, 2023

  • 顶点覆盖的重构及其它

    研究通过添加或删除至多 $l$ 个顶点，使得每个操作结果都是大小最多为 $k$ 的顶点覆盖的情况下，判断是否可以将给定的图 $G$ 中的一个顶点覆盖 $S$ 转换为另一个顶点覆盖 $T$。研究对问题在各种图类中的复杂性进行分类，其中表明该问题在二分图中仍然具有 W [1] -hard 度，在（正则的）度受限的图以及更普遍的稠度较小的图上为 NP-hard 但出于固定参数是可处理的，并且在树形图上和仙人掌图上（在某些其他限制下）是可多项式时间内可解决的。

    Feb, 2014

  • 反馈弧集锦标赛、肯尼等级聚合和中介集锦标赛的更快算法

    我们研究了三个问题的固定参数算法：Kemeny 排名聚合、反馈弧集锦标赛和在两点之间的锦标赛。

    Jun, 2010

  • 关于树、单圈图和仙人掌图的在线图探索

    探究搜索者搜索未知的加权无向图的问题，证明最近邻算法的竞争比率在树中为 θ(logn)，并研究参数范围内算法 Blocking 在单轮图上是 3-competitive，在仙人掌图上是 5/2+√2 约等于 3.91-competitive。

    Apr, 2020

  • 挖掘演化图中的频繁模式

    本文研究了具有标签的图中的频繁子图挖掘问题，提出了适用于增量和完全动态流设置的算法，以提取给定阈值下的高质量近似频繁 $k$- 顶点子图，通过保持一个均匀采样 $k$- 顶点子图组，并优化围绕更新的邻域探索过程，以及理论分析的支持，我们证明了所提出的算法相对于现有的最先进的解决方案可以产生高质量的结果。

    Sep, 2018

  • 稀疏图上的重构

    本研究针对两种古典的顶点子集问题 ISR 和 DSR，研究其重配置变体问题，同时提出一种固定参数可跟踪的算法来解决 ISR 和 DSR 问题。

    Feb, 2015

  • 关于近似支配集的参数化复杂性

    论文研究了基于参数的复杂度近似算法，通过建立通信复杂度和近似难度的关系，研究了支撑不同假设下 Label Cover 问题变种的近似难度。

    Nov, 2017