- 计算具有相同骨架的马尔可夫等价类的一个易于参数化的算法
给定一个无向图 G 作为输入,本文通过给出一个以树宽和图 G 的最大度数为参数的固定参数可行算法,为解决如何计算具有相同骨架 G 的不同 Markov 等价类的问题取得了进展。
- 条件独立图上的知识传播
本研究提出了在条件独立图上进行知识传播的算法,实验证明该技术在公开可用的 Cora 和 PubMed 数据集上优于现有技术。
- 图探索竞争问题的改进下界
通过访问顶点并返回起始位置的单一代理器的边权无向图探索,我们在 competitive ratio 上获得了 10/3 的改进下界,这与 Dobrev 的下限相比较,也适用于平面图。
- AAAI对称化有向图嵌入
该研究探索了一种针对有向图嵌入问题的两阶段方法,第一阶段对图进行对称化处理,第二阶段使用任何先进的(无向)图嵌入算法来嵌入所获得的对称图。
- 张量网络秩
该研究论文讨论了在低秩假设中,函数、矩阵或张量(在这种情况下,它们都是相同的对象)具有高秩的自然实例,给出了关于未定向图的新秩概念,并探讨了张量网络状态的不同 $G$-rank。
- 一种多项式时间逼近算法用于全节点网络可靠性
在无向图中,基于 “簇弹出” 算法的期望运行时间受输入规模的多项式限制,得到了全多项式时间随机逼近方案 (FPRAS) 来解决全终端网络可靠性问题。
- 关于图中的合并时间 —— 何时合并速度与相遇速度一样快?
该研究提出了一种强大的工具包,用于估计具有共同随机行走和混淆时间的随机游走在无向图上的汇聚时间和会合时间,并对相似类别的图形的汇聚时间和会合时间进行了完整的探索。
- 全色最短路径问题
该篇论文介绍了一种定义在无向图上的全色最短路径问题,它旨在寻找一条最短路径,在路径中每种颜色至少出现一次,假设图中的每个顶点都与一个已知的颜色相关联。该论文证明了这个问题是 NP-hard 的,并提出了用 LP 松弛,模拟退火,蚁群算法和遗 - 快速生成随机生成树和有效电阻度量
该论文提出了一个新的算法,用于在无向图中生成均匀随机生成树,算法利用随机生成树,随机游走和有效电阻的相互作用,以及设计与基础图的组合结构相关的算法方式,从而实现了高效的采样。
- 一种完整的任意时刻用于树宽算法
本文提出了一种基于分支界限算法的快速计算无向图树宽的算法 QuickBB,包括理论基础与算法实现,可以应用于任何无向图,并对该算法的实验结果进行了比较和分析。
- 随机决策网络中的相关性衰减
在考虑决策网络在无向图上进行决策的过程中,使用 Cavity Expansion 算法,对某些模型的最优解进行去中心化的求解,从而将 NP 难问题转化为可解问题并寻求了具有潜在的统计物理学,组合优化和网络经济应用价值的趋势。