2017/05/02 by Abdel-Rahman Madkour, Madkour, Abdel-Rahman, Phillip Nadolny +3
Computer Science · #90C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Management and Algorithms #Data Mining Algorithms and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.1705.00774
openalex publication_date 2017/05/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce a graph partitioning problem motivated by computational topology and propose two algorithms that produce approximate solutions. 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 the 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 then propose two approximation algorithms, one that uses a spectral clustering approach and another that employs a dynamic programming strategy, which produce near-optimal partitions on a family of test graphs. We describe these algorithms and analyze their empirical performance.