Nov, 2014

实践中的分支规约指数 / FPT 算法：顶点覆盖案例研究

PDF
TL;DR研究并比较了基于分支减枝算法在理论和实践方面的差异，证明了这些算法在现实应用中具有竞争力，以及理论研究对分支算法实际影响的作用。
branch-and-reduce algorithmstime complexitystate-of-the-art methodstheoretical researchvertex cover problem
发现论文，激发创造
  • 利用简化规则和数据结构：大规模图中最小顶点覆盖问题的局部搜索

    本文提出了一种本地搜索算法来解决实际大规模图上的最小顶点覆盖问题，其利用简化规则和数据结构来提高算法效率，并在各种真实世界的大规模图上进行了实验，结果显示比 MinVC 领域最好的本地搜索算法表现更好，也提供了一些关于一些知名启发式算法复杂度的有趣结果。

    Sep, 2015

  • 一种非马尔可夫算法的覆盖时间研究

    本文以理论角度为出发点，研究负反馈策略在遍历算法中的应用，论证该方法可以在任意图中提高搜索效率，并对经典 UCB 和 MCTS 算法提供新的见解。

    Jun, 2023

  • 解决实际大规模图中的最大权独立集问题

    本文提出了一种新的最大权独立集问题分支和缩减策略，结合核心化与局部搜索能够比局部搜索单独得出更高质量的解，通过实验表明，在实践中这种方法比现有的算法更加有效，可以处理高达数百万个顶点和边的实际问题。

    Oct, 2018

  • 多样化打击集的 FPT 算法

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

    Nov, 2019

  • 学习修剪：加速重复计算

    该研究提出了一种能够学习最大程度地修剪搜索空间的算法，从而在解决多次相似的计算问题时，能够大幅减少运行时间并保证准确解决问题。

    Apr, 2019

  • 基于连通图的成本转移方案

    本文提出了利用 minibucket elimination 和 message-passing updates 两种方法来划定图形模型中 MPE 查询边界的多种算法，采用混合式方法平衡两者优势，实验证明其在 PASCAL2 推理挑战中取得第一名。

    Oct, 2012

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

    研究了连接反馈顶点集（Connected Feedback Vertex Set）问题的参数化算法，论述了该问题在图论领域的应用，证明了在普通图上复杂度为 O (2^O (k) n^O (1))，在不包含固定图 H 的图上复杂度为 O (2^O (√k logk) n^O (1))，此外将 Group Steiner Tree 问题用作子程序，并认为其独立于其他算法，具有重要意义。

    Sep, 2009

  • 路径抽样：一种快速可证明的估计 4 元子图数量的方法

    本文介绍一种基于三路径采样和特殊剪枝技术的采样算法，可准确估算所有 4 个顶点模式子图的频率，并在容易实现和计算效率上优于传统枚举和采样算法。

    Nov, 2014

  • 顶点覆盖的重构及其它

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

    Feb, 2014

  • 反馈顶点集的参数化算法的实验评估

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

    Mar, 2018