[1] |
D. Bader, H. Meyerhenke, P. Sanders, and D. Wagner (Eds.). 2013. Graph Partitioning and Graph Clustering—10th DIMACS Impl. Challenge. Contemporary Mathematics, Vol. 588. AMS. 19-36. |
[2] |
M. Bender and M. Farach-Colton. 2000. The LCA problem revisited. In Proceedings of the 4th Latin American Symposium on Theoretical Informatics (LATIN’00). Springer-Verlag, 88-94. · Zbl 0959.68133 |
[3] |
C. Bichot and P. Siarry (Eds.). 2011. Graph Partitioning. Wiley. · Zbl 1242.05002 |
[4] |
T. N. Bui and C. Jones. 1993. A heuristic for reducing fill in sparse matrix factorization. In 6th SIAM Conference on Parallel Processing for Scientific Computing (PPSC). 445-452. |
[5] |
A. Buluç, H. Meyerhenke, I. Safro, P. Sanders, and C. Schulz. 2014. Recent Advances in Graph Partitioning. Technical Report arXiv:1311.3144. |
[6] |
J. Chen and I. Safro. 2011. Algebraic distance on graphs. SIAM J. Comput. 6 (2011), 3468-3490. · Zbl 1235.05042 |
[7] |
C. Chevalier and I. Safro. 2009. Comparison of coarsening schemes for multi-level graph partitioning. In Proceedings of Learning and Intelligent Optimization. |
[8] |
L. Costa, O. Oliveira, Jr., G. Travieso, F. Rodrigues, P. Villas Boas, L. Antiqueira, Matheus P. Viana, and L. Correa Rocha. 2011. Analyzing and modeling real-world phenomena with complex networks: A survey of applications. Adv. Phys. 60, 3 (2011), 329-412. |
[9] |
R. Diestel. 2012. Graph Theory (4th ed.). Graduate Texts in Mathematics, Vol. 173. Springer. |
[10] |
B. Fagginger Auer and R. Bisseling. 2013. Graph coarsening and clustering on the GPU. In Graph Partitioning and Graph Clustering. AMS and DIMACS. · Zbl 1271.68198 |
[11] |
P. Felzenszwalb and D. Huttenlocher. 2004. Efficient graph-based image segmentation. Int. J. Comput. Vision 59, 2 (2004), 167-181. · Zbl 1477.68505 |
[12] |
J. Fischer and V. Heun. 2006. Theoretical and practical improvements on the RMQ-problem with applications to LCA and LCE. In Proceedings of the 16th Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science, Vol. 4009. Springer, 36-48. · Zbl 1196.68068 |
[13] |
W. Fung, R. Hariharan, N. Harvey, and D. Panigrahi. 2011. A general framework for graph sparsification. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC’11). ACM, 71-80. · Zbl 1288.68118 |
[14] |
M. Garey, D. Johnson, and L. Stockmeyer. 1974. Some simplified NP-Complete problems. In Proceedings of the 6th ACM Symposium on Theory of Computing (STOC’74). ACM, 47-63. |
[15] |
R. Glantz, H. Meyerhenke, and C. Schulz. 2014. Tree-based coarsening and partitioning of complex networks. In 13th International Symposium on Experimental Algorithms, (SEA 2014), J. Gudmundson and J. Katajainen (Eds.). Springer, 364-375. · Zbl 1365.68355 |
[16] |
L. Grady and E. Schwartz. 2006. Isoperimetric graph partitioning for image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 28, 3 (2006), 469-475. |
[17] |
Y. Haxhimusa, R. Glantz, M. Saib, G. Langs, and W. Kropatsch. 2002. Logarithmic tapering graph pyramid. In Proceedings of the DAGM Symposium 2002, Lecture Notes in Computer Science, Vol. 2449, Luc Van Gool (Ed.). Springer, 117-124. · Zbl 1017.68716 |
[18] |
Bruce Hendrickson and Tamara G. Kolda. 2000. Graph partitioning models for parallel computing. Parallel Comput. 26, 12 (2000), 1519-1534. · Zbl 0948.68130 |
[19] |
B. Hendrickson and R. Leland. 1995. A multi-level algorithm for partitioning graphs. In Proceedings of Supercomputing’95. ACM, 28 (CD). · Zbl 0816.68093 |
[20] |
M. Holtgrewe, P. Sanders, and C. Schulz. 2010. Engineering a scalable high quality graph partitioner. In 24th International Parallel and Distributed Processing Symposium (IPDPS). |
[21] |
J. Hopcroft and R. Tarjan. 1973. Efficient algorithms for graph manipulation. Comm. ACM 16 (1973), 372-378. |
[22] |
D. Jungnickel. 2005. Graphs, Networks and Algorithms (2nd. ed.). Algorithms and Computation in Mathematics, Vol. 5. Springer, Berlin. · Zbl 1061.05001 |
[23] |
R. Kannan, S. Vempala, and A. Vetta. 2004. On clusterings: Good, bad and spectral. J. ACM 51, 3 (2004), 497-515. · Zbl 1192.05160 |
[24] |
G. Karypis and V. Kumar. 1998. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20, 1 (1998), 359-392. · Zbl 0915.68129 |
[25] |
W. Kropatsch. 1997. Equivalent contraction kernels to build dual irregular pyramids. Advances in Computer Science, Advances in Computer Vision (1997), pp. 99-107. · Zbl 0899.68105 |
[26] |
J. Leskovec. 2014. Stanford Network Analysis Package (SNAP). (2014). http://snap.stanford.edu/index.html. |
[27] |
J. Maue and P. Sanders. 2007. Engineering algorithms for approximate weighted matching. In Proceedings of the 6th International Workshop on Experimental Algorithms (WEA’07), Lecture Notes in Computer Science, Vol. 4525. Springer-Verlag, 242-255. · Zbl 1203.68317 |
[28] |
C. Mavroforakis, R. Garcia-Lebron, I. Koutis, and E. Terzi. 2015. Spanning edge centrality: Large-scale computation and applications. In Proceedings of the 24th International World Wide Web Conference (WWW 2015). International World Wide Web Conferences Steering Committee (IW3C2), ACM. |
[29] |
H. Meyerhenke, B. Monien, and S. Schamberger. 2006. Accelerating shape optimizing load balancing for parallel FEM simulations by algebraic multigrid. In Proceedings of the 20th International Parallel and Distributed Processing Symposium (IPDPS). 57. |
[30] |
H. Meyerhenke, B. Monien, and S. Schamberger. 2009. Graph partitioning and disturbed diffusion. Parallel Comput. 35, 10-11 (2009), 544-569. |
[31] |
H. Meyerhenke, P. Sanders, and C. Schulz. 2014. Partitioning complex networks via size-constrained clustering. In 13th International Symposium on Experimental Algorithms (SEA’14), J. Gudmundson and J. Katajainen (Eds.). Springer, 351-363. · Zbl 1360.90305 |
[32] |
M. Newman. 2010. Networks: An Introduction. Oxford University Press, Inc., New York. · Zbl 1195.94003 |
[33] |
V. Osipov and P. Sanders. 2010. N-Level graph partitioning. In Proceedings of the 18th European Symposium on Algorithms (ESA’10). 278-289. · Zbl 1287.05152 |
[34] |
D. Pritchard and R. Thurimella. 2011. Fast computation of small cuts via cycle space sampling. ACM Trans. Algorithms 7, 4 (2011), 46:1-46:30. · Zbl 1295.68205 |
[35] |
U. Raghavan, R. Albert, and S. Kumara. 2007. Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E 76, 3 (2007), 036106. |
[36] |
I. Safro, P. Sanders, and C. Schulz. 2012. Advanced coarsening schemes for graph partitioning. In Proceedings of the 11th International Symposium on Experimental Algorithms. Springer, 369-380. · Zbl 1347.68355 |
[37] |
P. Sanders and C. Schulz. 2013. Think locally, act globally: Highly balanced graph partitioning. In Proceedings of the 12th International Symposium on Experimental Algorithms. Springer, 164-175. |
[38] |
P. Sanders and C. Schulz. 2014. KaHIP—Karlsruhe High Qualtity Partitioning Homepage. (2014). http://algo2.iti.kit.edu/documents/kahip/index.html. |
[39] |
C. Schulz. 2013. Hiqh Quality Graph Partititioning. Ph.D. dissertation. Karlsruhe Institute of Technology. |
[40] |
A. Soper, C. Walshaw, and M. Cross. 2004. A combined evolutionary search and multilevel optimisation approach to graph partitioning. J. Global Opt. 29, 2 (2004), 225-241. · Zbl 1084.90049 |
[41] |
D. Spielman and N. Srivastava. 2008. Graph sparsification by effective resistances. CoRR abs/0803.0929 (2008). http://arxiv.org/abs/0803.0929 · Zbl 1231.68184 |
[42] |
R. Tarjan. 1972. Depth-first search and linear graph algorithms. J. Comput. 1 (1972), 146-160. · Zbl 0251.05107 |
[43] |
J. Wassenberg, W. Middelmann, and P. Sanders. 2009. An efficient parallel algorithm for graph-based image segmentation. In Proceedings of the 13th International Conference on Computer Analysis of Images and Patterns. 1003-1010. |