Jul, 2019

H - 自由图中最大权独立集问题的拟多项式时间逼近方案

PDF
TL;DR本文研究的是在 $H$-free 图中最大独立集问题的复杂度，通过提出近似算法和精确算法，对一些情况下的这一问题做出了更好的可解性结果。
maximum independent setnp-hardtractability$h$-free graphsapproximation algorithm
发现论文，激发创造
  • 最大独立集合的最佳低阶硬度

    研究在稀疏的 Erdős-Rényi 随机图中寻找大独立集的算法任务，其中低次多项式算法可以找到半优大小的独立集，但不大于此规模。

    Oct, 2020

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

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

    Oct, 2018

  • 最大独立集的精确算法

    本研究提出了一种基于低度图的层次快速算法，可以在多项式空间复杂度内解决最大独立集问题，并得到了在不同最大度的图形中最大独立集问题的改进算法。

    Dec, 2013

  • 大规模最大独立集问题的元启发式算法

    针对实际的车辆路径问题，研究了最大权独立集问题，通过开发一个新的本地搜索算法，该算法使用了先前文献中未描述的更广泛的简单局部搜索运算和数据结构，引入了路径重新链接的新变体来避免局部最优解以及一种新的交替增广路径局部搜索移动来提高算法性能。

    Mar, 2022

  • 最大独立集问题的自适应重复交集约简局部搜索

    本文研究了应用广泛的 NP-hard 问题之一，最大独立集问题（ M IS），提出了局部搜索框架 ARIR 及其三种算法，采用三种不同的减少策略，在五组基准测试中显示出明显的优越性。

    Aug, 2022

  • 精确重量子图与 k-Sum 猜想

    研究 Exact-Weight-H 问题的复杂性，发现与 k-Sum 问题有强关联，并且提供了紧密的上下界解。如果改进 Exact-Weight-4-Path 或者 Exact-Weight-5-Path 的 O (n^3) 复杂度上界，则能够改进 3-Sum、5-Sum、All-Pairs Shortest Paths 和其他基础问题的算法，而检测版本和最小权重版本可以在 O (n^2) 时间内轻松完成。此外，任何以下三个问题的更快算法都将带来其他两个问题的更快算法：3-Sum，Exact-Weight-3-Matching 和 Exact-Weight-3-Star。

    Apr, 2013

  • CONGEST 模型二次和接近二次的下界

    该研究给出在 CONGEST 模型中自然图问题的第一个超线性下界，并回答了长期以来的一个开放性问题，特别地，证明任何精确计算最小顶点覆盖或最大独立集的算法都需要在最坏情况下花费 Ω(n²/log²n) 轮，这样强的下界不仅局限于 NP 困难问题。

    May, 2017

  • 大规模寻找近似最优独立集

    本文提出一种应用进化算法和核技术求解大规模稀疏网络独立集问题的高效算法，并通过移除可能出现在大独立集中的顶点来加速计算，并在此基础上在比文献中更大的实例上计算高质量的独立集。

    Sep, 2015

  • 利用独立集预言机进行边缘估计

    本研究探讨了使用独立集合查询进行图边估计的问题，并提出了两种算法来估计 n 个顶点的图中边的数量。

    Nov, 2017

  • 大规模稀疏图上最大团问题的快速算法

    本研究提出了一种基于新颖的修剪技术的精确算法，能够在大型稀疏图中快速找到最大团。实验结果表明，在大多数情况下，我们的算法比现有算法快数个数量级，并且我们还提出了一种能够在最优或接近最优解的情况下比精确算法快数个数量级的启发式变体。

    Sep, 2012