Jul, 2017

二分图独立集重构的复杂度

PDF
TL;DR本文研究了在三种常见改变模式下的独立集重新配置问题，发现在 Token Jumping 或 Token addition/removal 模式下问题是 NP-complete，而在 Token Sliding 模式下问题仍然保持是 PSPACE-complete。
发现论文，激发创造
  • 稀疏图上的重构

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

    Feb, 2015

  • 基于答集编程的有界组合重新配置

    我们提出了一种称为有界组合重新配置的方法，用于基于 Answer Set Programming（ASP）解决组合重新配置问题。我们设计和实现了有界组合重新配置，并提出了独立集重新配置问题的 ASP 编码，这是最研究的组合重新配置问题之一。通过考虑 CoRe Challenge 2022 的所有实例，我们进行了实证分析。

    Jul, 2023

  • 布尔公式解空间中的最短重构路径

    本研究研究了用 flip 操作实现布尔公式中一个满足赋值到另一个满足赋值的最短转换问题的复杂度，结果表明该问题的复杂度可能为 P、NP-complete 或 PSPACE-complete。

    Apr, 2014

  • 最大独立集的精确算法

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

    Dec, 2013

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

    本文研究的是在 $H$-free 图中最大独立集问题的复杂度，通过提出近似算法和精确算法，对一些情况下的这一问题做出了更好的可解性结果。

    Jul, 2019

  • 重新规划最短路径的复杂性

    研究了最短路径重构问题在不同类型的图中的复杂度，其中爪图和弦图可以用多项式时间解决并具有线性长度，同时提供了计算孤立路径数量的算法。

    Sep, 2010

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

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

    Nov, 2017

  • 顶点覆盖的重构及其它

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

    Feb, 2014

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

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

    Oct, 2018

  • 通过非确定性约束逻辑模型计算的滑块拼图和其他问题的 PSPACE 完备性

    本文介绍了一种基于加权有向图和最小流限制的非确定性计算模型，并且通过一系列特例的证明和简单归约，证明了该模型可以被用于解决复杂的运动规划问题，包括障碍物移动、滑动积木等。

    May, 2002