一种寻找图形子图的实用启发式方法
本文提出了交织的量子绝热架构设计问题,要求构建一个满足所有已知物理约束的硬件图 U,同时允许一种高效的 minor-embedding 算法,最后给出了一个最佳的完全图 minor。
Jan, 2010
本文探讨了通过扫描顶点邻域,计算每个顶点的聚类系数并输出最佳子图来提取大的准簇的简单方法,证明了现实世界图的两个重要特征意味着存在具有高边密度的大型顶点邻域。这种方法的实现需要对图中的三角形进行计数,这在图挖掘中是一个被深入研究的问题。经过实际测试,该方法揭示了一个惊人的事实:顶点邻域包括中等大小的极大团,而最佳邻域的密度往往比用于最大化子图密度的专用算法产生的子图优越。对于聚类系数较小的图,我们证明可以使用局部搜索方法来 “增长” 更大的团和准团。与最坏情况理论结果相反,从实际图中挖掘中等大小的团和准团通常不是一个困难问题,并且激励了进一步研究这些实证成功的更好解释。
Aug, 2020
该研究介绍了使用原生团子图的方法,将任意的二体相互作用构造成一种能被 D-Wave 量子退火处理器求解的 Ising 自旋问题,并给出了一种多项式时间复杂度的算法来寻找给定的感应子图中的最大本地团子图。
Jul, 2015
研究使用图形草图和本地采样构建的数据结构来处理在消除过程中矩阵近似填充度的问题,并导出可用于生成近似的贪婪最小度量排序的近线性时间算法,以及解决了内部随机性导致的失败问题。
Apr, 2018
本文提出了一种本地搜索算法来解决实际大规模图上的最小顶点覆盖问题,其利用简化规则和数据结构来提高算法效率,并在各种真实世界的大规模图上进行了实验,结果显示比 MinVC 领域最好的本地搜索算法表现更好,也提供了一些关于一些知名启发式算法复杂度的有趣结果。
Sep, 2015
本文研究了大规模图的本地算法设计并提出了一种本地聚类算法,该算法可在几乎线性的时间内找到较好的簇,并基于该聚类算法提出了一种划分算法,进而设计了求解对称对角占优矩阵中线性系统的近线性算法,还提出了其他相关结果。
Sep, 2008
本文使用少数嵌入和参数设置,通过实现 Ising 自旋 - 1/2 哈密顿量的绝热量子计算机,证明了在量子硬件图 U 中,可以解决图 G 上的 NP-hard 二次无约束二进制优化问题。
Apr, 2008
本文提出了利用 minibucket elimination 和 message-passing updates 两种方法来划定图形模型中 MPE 查询边界的多种算法,采用混合式方法平衡两者优势,实验证明其在 PASCAL2 推理挑战中取得第一名。
Oct, 2012