Finding Minimal Spanning Forests in a Grap
Finding Minimal Spanning Forests in a Grap
复制标题
DOI：
--
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
Abdelrahman Madkour;P. Nadolny;Matthew L. Wright
中科院分区：
文献类型：
--
作者：
Abdelrahman Madkour;P. Nadolny;Matthew L. Wright
我们提出了两种算法来解决由计算拓扑驱动的图划分问题。具体来说，给定一个带权无向图 $G$ 和一个正整数 $k$，我们希望在 $G$ 中找到 $k$ 个不相交树，使得 $G$ 的每个顶点都包含在其中一棵树中，并且最大树的权重尽可能小。我们无法在图划分文献中找到这个问题，但我们证明这个问题是 NP 完全的。我们提出了两种近似算法，一种使用谱聚类方法，另一种采用动态编程策略，在一系列测试图上产生接近最优的分区。我们描述这些算法并分析它们的实证性能。
We propose two algorithms for solving a graph partitioning problem motivated by computational topology. Specifically, given a weighted, undirected graph $G$ and a positive integer $k$, we desire to find $k$ disjoint trees within $G$ such that each vertex of $G$ is contained in one of the trees and the weight of largest tree is as small as possible. We are unable to find this problem in the graph partitioning literature, but we show that the problem is NP-complete. We propose two approximation algorithms, one that uses a spectral clustering approach and another that employs a dynamic programming strategy, that produce near-optimal partitions on a family of test graphs. We describe these algorithms and analyze their empirical performance.