Finding Minimum Spanning Forests in a Graph

Preprint English OPEN
Madkour, Abdel-Rahman; Nadolny, Phillip; Wright, Matthew;
  • Subject: Mathematics - Combinatorics | 90C35 | Computer Science - Data Structures and Algorithms

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$ ... View more
  • References (8)

    [1] E. Anderson, et al., LAPACK Users' Guide, 3rd Edition, SIAM, 1999,

    [2] S. Dasgupta, C. Papadimitriou, and U. Vazirani, Algorithms, McGraw Hill, 2008.

    [3] P.-O. Fj¨allstro¨m, “Algorithms for Graph Partitioning: A Survey”, Link¨oping Electronic Articles in Computer and Information Science, Vol. 3. (1998),

    [4] M. Lesnick, M. Wright, “Interactive Visualization of 2-D Persistence Modules”, preprint,

    [5] M. I. Malinen, P. Fr¨anti, “Balanced K-Means ing”, Lecture Notes in Computer Science, 8621(2014),

    for Clusterpp. 32-41,

    [6] S. Pettie, V. Ramachandran, “Computing Shortest Paths parisons and Additions”, Proceedings of the Thirteenth SIAM Symposium on Discrete Algorithms, SODA 2002,

    Segmentation”, pp. 888-905, [8] D. Xu, Y. Tian, “A Comprehensive Survey of Clustering Algorithms”, Ann. Data Sci. (2015) 2: 165,

  • Related Research Results (1)
    Inferred by OpenAIRE
    Minimal-Spanning-Trees software on GitHub
  • Metrics
Share - Bookmark