Finding Minimum Spanning Forests in a Graph

Preprint English OPEN
Madkour, Abdel-Rahman; Nadolny, Phillip; Wright, Matthew;
(2017)
  • 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, http://dx.doi.org/10.1137/1.9780898719604.

    [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), http://www.ep.liu.se/ea/cis/1998/010/cis98010.pdf.

    [4] M. Lesnick, M. Wright, “Interactive Visualization of 2-D Persistence Modules”, preprint, http://arxiv.org/abs/1512.00180.

    [5] M. I. Malinen, P. Fr¨anti, “Balanced K-Means ing”, Lecture Notes in Computer Science, 8621(2014), http://link.springer.com/chapter/10.1007/978-3-662-44415-3_4.

    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, http://dl.acm.org/citation.cfm?id=545381.545417.

    Segmentation”, pp. 888-905, [8] D. Xu, Y. Tian, “A Comprehensive Survey of Clustering Algorithms”, Ann. Data Sci. (2015) 2: 165, http://link.springer.com/article/10.1007/s40745-015-0040-1.

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