Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Engineering a Lightweight and Efficient Local Search SAT Solver Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Recent Advances in Graph Partitioning

verfasst von : Aydın Buluç, Henning Meyerhenke, Ilya Safro, Peter Sanders, Christian Schulz

Erschienen in: Algorithm Engineering

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We survey recent trends in practical algorithms for balanced graph partitioning, point to applications and discuss future research directions.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Theoretical Analysis of the k-Means Algorithm – A Survey
Nächstes Kapitel How to Generate Randomized Roundings with Dependencies and How to Derandomize Them
Fußnoten
1
Sometimes more complex models are used to model lanes, turn costs etc.
 
Literatur
1.
Abou-Rjeili, A., Karypis, G.: Multilevel algorithms for partitioning power-law graphs. In: 20th International Parallel and Distributed Processing Symposium (IPDPS). IEEE (2006)
2.
Akhremtsev, Y., Sanders, P., Schulz, C.: (Semi-)external algorithms for graph partitioning and clustering. In: 15th Workshop on Algorithm Engineering and Experimentation (ALENEX), pp. 33–43 (2015)
3.
Andersen, R., Lang, K.J.: An algorithm for improving graph partitions. In: 19th ACM-SIAM Symposium on Discrete Algorithms, pp. 651–660 (2008)
4.
5.
Armbruster, M.: Branch-and-cut for a semidefinite relaxation of large-scale minimum bisection problems. Ph.D. thesis, U. Chemnitz (2007)
6.
Armbruster, M., Fügenschuh, M., Helmberg, C., Martin, A.: A comparative study of linear and semidefinite branch-and-cut methods for solving the minimum graph bisection problem. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol. 5035, pp. 112–124. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-68891-4_​8 CrossRef
7.
Arora, S., Hazan, E., Kale, S.: O(\(\sqrt{\log n}\)) approximation to sparsest cut in Õ(n\(^{\text{2 }}\)) time. SIAM J. Comput. 39(5), 1748–1771 (2010)MathSciNetMATHCrossRef
8.
Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings and graph partitioning. In: 36th ACM Symposium on the Theory of Computing (STOC), pp. 222–231 (2004)
9.
Aubanel, E.: Resource-aware load balancing of parallel applications. In: Udoh, E., Wang, F.Z. (eds.) Handbook of Research on Grid Technologies and Utility Computing: Concepts for Managing Large-Scale Applications, pp. 12–21. Information Science Reference - Imprint of: IGI Publishing, May 2009
10.
Auer, B.F., Bisseling, R.H.: Graph coarsening and clustering on the GPU. In: Bader et al. [13], pp. 19–36
11.
12.
Bader, D.A., Meyerhenke, H., Sanders, P., Schulz, C., Kappes, A., Wagner, D.: Benchmarking for graph clustering and graph partitioning. In: Encyclopedia of Social Network Analysis and Mining (to appear)
13.
Bader, D.A., Meyerhenke, H., Sanders, P., Wagner, D. (eds.): Graph Partitioning and Graph Clustering – 10th DIMACS Impl. Challenge, Contemporary Mathematics, vol. 588. AMS, Boston (2013)
14.
15.
Barnard, S.T., Simon, H.D.: A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. In: 6th SIAM Conference on Parallel Processing for Scientific Computing, pp. 711–718 (1993)
16.
Benlic, U., Hao, J.K.: An effective multilevel memetic algorithm for balanced graph partitioning. In: 22nd IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp. 121–128 (2010)
17.
Benlic, U., Hao, J.K.: A multilevel memetic approach for improving graph \(k\)-partitions. IEEE Trans. Evol. Comput. 15(5), 624–642 (2011)CrossRef
18.
Benlic, U., Hao, J.K.: An effective multilevel tabu search approach for balanced graph partitioning. Comput. Oper. Res. 38(7), 1066–1075 (2011)MathSciNetMATHCrossRef
19.
20.
Bhatele, A., Kale, L.: Heuristic-based techniques for mapping irregular communication graphs to mesh topologies. In: 13th Conference on High Performance Computing and Communications (HPCC), pp. 765–771 (2011)
21.
Bhatele, A., Jain, N., Gropp, W.D., Kale, L.V.: Avoiding hot-spots on two-level Direct networks. In: ACM/IEEE Conference for High Performance Computing, Networking, Storage and Analysis (SC), pp. 76:1–76:11. ACM (2011)
22.
Bichot, C., Siarry, P. (eds.): Graph Partitioning. Wiley, Hoboken (2011)MATH
23.
Bichot, C.E.: A new method, the fusion fission, for the relaxed \(k\)-way graph partitioning problem, and comparisons with some multilevel algorithms. J. Math. Model. Algorithms 6(3), 319–344 (2007)MathSciNetMATHCrossRef
24.
Birn, M., Osipov, V., Sanders, P., Schulz, C., Sitchinava, N.: Efficient parallel and external matching. In: Wolf, F., Mohr, B., Mey, D. (eds.) Euro-Par 2013. LNCS, vol. 8097, pp. 659–670. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-40047-6_​66 CrossRef
25.
Boman, E.G., Devine, K.D., Rajamanickam, S.: Scalable matrix computations on large scale-free graphs using 2D graph partitioning. In: ACM/IEEE Conference for High Performance Computing, Networking, Storage and Analysis (SC) (2013)
26.
Boppana, R.B.: Eigenvalues and graph bisection: an average-case analysis. In: 28th Symposium on Foundations of Computer Science (FOCS), pp. 280–285 (1987)
27.
28.
Brunetta, L., Conforti, M., Rinaldi, G.: A branch-and-cut algorithm for the equicut problem. Math. Program. 78(2), 243–263 (1997)MathSciNetMATHCrossRef
29.
Bui, T., Chaudhuri, S., Leighton, F., Sipser, M.: Graph bisection algorithms with good average case behavior. Combinatorica 7, 171–191 (1987)MathSciNetCrossRef
30.
Buluç, A., Gilbert, J.R.: The combinatorial BLAS: design, implementation, and applications. Int. J. High Perform. Comput. Appl. 25(4), 496–509 (2011)CrossRef
31.
Buluç, A., Madduri, K.: Graph partitioning for scalable distributed graph computations. In: Bader et al. [13], pp. 83–102
32.
Camilus, K.S., Govindan, V.K.: A review on graph based segmentation. IJIGSP 4, 1–13 (2012)CrossRef
33.
Catalyurek, U., Aykanat, C.: A hypergraph-partitioning approach for coarse-grain decomposition. In: ACM/IEEE Conference on Supercomputing (SC). ACM (2001)
34.
Catalyurek, U., Boman, E., et al.: Hypergraph-based dynamic load balancing for adaptive scientific computations. In: 21st International Parallel and Distributed Processing Symposium (IPDPS). IEEE (2007)
35.
Çatalyürek, Ü., Aykanat, C.: PaToH: partitioning tool for hypergraphs. In: Padua, D. (ed.) Encyclopedia of Parallel Computing. Springer, Heidelberg (2011)
36.
Chan, S.Y., Ling, T.C., Aubanel, E.: The impact of heterogeneous multi-core clusters on graph partitioning: an empirical study. Cluster Comput. 15(3), 281–302 (2012)CrossRef
37.
Chardaire, P., Barake, M., McKeown, G.P.: A PROBE-based heuristic for graph partitioning. IEEE Trans. Comput. 56(12), 1707–1720 (2007)MathSciNetCrossRef
38.
39.
Chevalier, C., Pellegrini, F.: Improvement of the efficiency of genetic algorithms for scalable parallel graph partitioning in a multi-level framework. In: Nagel, W.E., Walter, W.V., Lehner, W. (eds.) Euro-Par 2006. LNCS, vol. 4128, pp. 243–252. Springer, Heidelberg (2006). doi:10.​1007/​11823285_​25 CrossRef
40.
Chevalier, C., Pellegrini, F.: PT-Scotch: a tool for efficient parallel graph ordering. Parallel Comput. 34(6), 318–331 (2008)MathSciNetCrossRef
41.
Chevalier, C., Safro, I.: Comparison of coarsening schemes for multi-level graph partitioning. In: Proceedings Learning and Intelligent Optimization (2009)
42.
Chierichetti, F., Kumar, R., Lattanzi, S., Mitzenmacher, M., Panconesi, A., Raghavan, P.: On compressing social networks. In: 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 219–228 (2009)
43.
Chu, S., Cheng, J.: Triangle listing in massive networks and its applications. In: 17th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 672–680 (2011)
44.
Comellas, F., Sapena, E.: A multiagent algorithm for graph partitioning. In: Rothlauf, F., Branke, J., Cagnoni, S., Costa, E., Cotta, C., Drechsler, R., Lutton, E., Machado, P., Moore, J.H., Romero, J., Smith, G.D., Squillero, G., Takagi, H. (eds.) EvoWorkshops 2006. LNCS, vol. 3907, pp. 279–285. Springer, Heidelberg (2006). doi:10.​1007/​11732242_​25 CrossRef
45.
Cong, J., Shinnerl, J.: Multilevel Optimization in VLSICAD. Springer, Heidelberg (2003)MATHCrossRef
46.
47.
Dean, J., Ghemawat, S.: MapReduce: simplified data processing on large clusters. In: 6th Symposium on Operating System Design and Implementation (OSDI), pp. 137–150. USENIX (2004)
48.
Delling, D., Goldberg, A.V., Pajor, T., Werneck, R.F.: Customizable route planning. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 376–387. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-20662-7_​32 CrossRef
49.
Delling, D., Goldberg, A.V., Razenshteyn, I., Werneck, R.F.: Exact combinatorial branch-and-bound for graph bisection. In: 12th Workshop on Algorithm Engineering and Experimentation (ALENEX), pp. 30–44 (2012)
50.
Delling, D., Goldberg, A.V., et al.: Graph partitioning with natural cuts. In: 25th International Parallel and Distributed Processing Symposium (IPDPS), pp. 1135–1146 (2011)
51.
52.
Delling, D., Werneck, R.F.: Faster customization of road networks. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 30–42. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-38527-8_​5 CrossRef
53.
54.
Guo, D., Ke Liao, H.J.: Power system reconfiguration based on multi-level graph partitioning. In: 7th International Conference, GIScience 2012 (2012)
55.
Diekmann, R., Monien, B., Preis, R.: Using helpful sets to improve graph bisections. In: Interconnection Networks and Mapping and Scheduling Parallel Computations, vol. 21, pp. 57–73 (1995)
56.
Diekmann, R., Preis, R., Schlimbach, F., Walshaw, C.: Shape-optimized mesh partitioning and load balancing for parallel adaptive FEM. Parallel Comput. 26, 1555–1581 (2000)MATHCrossRef
57.
Diekmann, R., Preis, R., Schlimbach, F., Walshaw, C.: Shape-optimized mesh partitioning and load balancing for parallel adaptive FEM. Parallel Comput. 26(12), 1555–1581 (2000)MATHCrossRef
58.
Donath, W.E., Hoffman, A.J.: Algorithms for partitioning of graphs and computer logic based on eigenvectors of connection matrices. IBM Tech. Discl. Bull. 15(3), 938–944 (1972)
59.
60.
Donde, V., Lopez, V., Lesieutre, B., Pinar, A., Yang, C., Meza, J.: Identification of severe multiple contingencies in electric power networks. In: 37th N. A. Power Symposium, pp. 59–66. IEEE (2005)
61.
Drake, D., Hougardy, S.: A simple approximation algorithm for the weighted matching problem. Inf. Process. Lett. 85, 211–213 (2003)MathSciNetMATHCrossRef
62.
Drake Vinkemeier, D.E., Hougardy, S.: A linear-time approximation algorithm for weighted matchings in graphs. ACM Trans. Algorithms 1(1), 107–122 (2005)MathSciNetMATHCrossRef
63.
Duan, R., Pettie, S., Su, H.H.: Scaling Algorithms for Approximate and Exact Maximum Weight Matching. CoRR abs/1112.0790 (2011)
64.
Dutt, S.: New faster Kernighan-Lin-type graph-partitioning algorithms. In: 4th IEEE/ACM Conference on Computer-Aided Design, pp. 370–377 (1993)
65.
Even, G., Naor, J.S., Rao, S., Schieber, B.: Fast approximate graph partitioning algorithms. SIAM J. Comput. 28(6), 2187–2214 (1999)MathSciNetMATHCrossRef
66.
Fagginger Auer, B.O., Bisseling, R.H.: Abusing a hypergraph partitioner for unweighted graph partitioning. In: Bader et al. [13], pp. 19–35
67.
68.
Feige, U., Krauthgamer, R.: A polylogarithmic approximation of the minimum bisection. SIAM J. Comput. 31(4), 1090–1118 (2002)MathSciNetMATHCrossRef
69.
Feldmann, A.E., Widmayer, P.: An \(\cal{O}(n^4)\) time algorithm to compute the bisection width of solid grid graphs. In: Demetrescu, C., Halldórsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 143–154. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-23719-5_​13 CrossRef
70.
Felner, A.: Finding optimal solutions to the graph partitioning problem with heuristic search. Ann. Math. Artif. Intell. 45, 293–322 (2005)MathSciNetMATHCrossRef
71.
Ferreira, C.E., Martin, A., De Souza, C.C., Weismantel, R., Wolsey, L.A.: The node capacitated graph partitioning problem: a computational study. Math. Program. 81(2), 229–256 (1998)MathSciNetMATHCrossRef
72.
Fiduccia, C.M., Mattheyses, R.M.: A linear-time heuristic for improving network partitions. In: 19th Conference on Design Automation, pp. 175–181 (1982)
73.
Fiedler, M.: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czech. Math. J. 25(4), 619–633 (1975)MathSciNetMATH
74.
Fietz, J., Krause, M.J., Schulz, C., Sanders, P., Heuveline, V.: Optimized hybrid parallel lattice Boltzmann fluid flow simulations on complex geometries. In: Kaklamanis, C., Papatheodorou, T., Spirakis, P.G. (eds.) Euro-Par 2012. LNCS, vol. 7484, pp. 818–829. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-32820-6_​81 CrossRef
75.
76.
Fortunato, S.: Community Detection in Graphs. CoRR abs/0906.0612 (2009)
77.
Fourestier, S., Pellegrini, F.: Adaptation au repartitionnement de graphes d’une méthode d’optimisation globale par diffusion. In: RenPar’20 (2011)
78.
Galinier, P., Boujbel, Z., Fernandes, M.C.: An efficient memetic algorithm for the graph partitioning problem. Ann. Oper. Res. 191(1), 1–22 (2011)MathSciNetMATHCrossRef
79.
Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete problems. In: 6th ACM Symposium on Theory of Computing, pp. 47–63. STOC, ACM (1974)
80.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)MATH
81.
George, A., Liu, J.W.H.: Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall, Upper Saddle River (1981)MATH
82.
Ghazinour, K., Shaw, R.E., Aubanel, E.E., Garey, L.E.: A linear solver for benchmarking partitioners. In: 22nd IEEE International Symposium on Parallel and Distributed Processing (IPDPS), pp. 1–8 (2008)
83.
Gilbert, J.R., Miller, G.L., Teng, S.H.: Geometric mesh partitioning: implementation and experiments. SIAM J. Sci. Comput. 19(6), 2091–2110 (1998)MathSciNetMATHCrossRef
84.
Glantz, R., Meyerhenke, H., Noe, A.: Algorithms for mapping parallel processes onto grid and torus architectures. In: Proceedings of the 23rd Euromicro International Conference on Parallel, Distributed and Network-Based Processing (2015, to appear). Preliminary version: http://​arxiv.​org/​abs/​1411.​0921
85.
Glantz, R., Meyerhenke, H., Schulz, C.: Tree-based coarsening and partitioning of complex networks. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 364–375. Springer, Heidelberg (2014). doi:10.​1007/​978-3-319-07959-2_​31
86.
87.
88.
Goldschmidt, O., Hochbaum, D.S.: A polynomial algorithm for the \(k\)-cut problem for fixed \(k\). Math. Oper. Res. 19(1), 24–37 (1994)MathSciNetMATHCrossRef
89.
Grady, L., Schwartz, E.L.: Isoperimetric graph partitioning for image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 28, 469–475 (2006)CrossRef
90.
Gregor, D., Lumsdaine, A.: The parallel BGL: a generic library for distributed graph computations. In: Parallel Object-Oriented Scientific Computing (POOSC) (2005)
91.
Gutfraind, A., Meyers, L.A., Safro, I.: Multiscale Network Generation. CoRR abs/1207.4266 (2012)
92.
Hager, W.W., Hungerford, J.T., Safro, I.: A multilevel bilinear programming algorithm for the vertex separator problem. CoRR abs/1410.4885 (2014). arXiv:​1410.​4885
93.
Hager, W.W., Krylyuk, Y.: Graph partitioning and continuous quadratic programming. SIAM J. Discrete Math. 12(4), 500–523 (1999)MathSciNetMATHCrossRef
94.
95.
96.
Hendrickson, B.: Graph partitioning and parallel solvers: has the emperor no clothes? In: Ferreira, A., Rolim, J., Simon, H., Teng, S.-H. (eds.) IRREGULAR 1998. LNCS, vol. 1457, pp. 218–225. Springer, Heidelberg (1998). doi:10.​1007/​BFb0018541 CrossRef
97.
Hendrickson, B., Leland, R.: A multilevel algorithm for partitioning graphs. In: ACM/IEEE Conference on Supercomputing 1995 (1995)
98.
Hendrickson, B., Leland, R.: An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM J. Sci. Comput. 16(2), 452–469 (1995)MathSciNetMATHCrossRef
99.
Hendrickson, B., Leland, R., Driessche, R.V.: Enhancing data locality by using terminal propagation. In: 29th Hawaii International Conference on System Sciences (HICSS 2009), vol. 1, p. 565. Software Technology and Architecture (1996)
100.
101.
Hoefler, T., Snir, M.: Generic topology mapping strategies for large-scale parallel architectures. In: ACM International Conference on Supercomputing (ICS 2011), pp. 75–85. ACM (2011)
102.
Holtgrewe, M., Sanders, P., Schulz, C.: Engineering a scalable high quality graph partitioner. In: 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 1–12 (2010)
103.
Hromkovič, J., Monien, B.: The bisection problem for graphs of degree 4 (configuring transputer systems). In: Tarlecki, A. (ed.) MFCS 1991. LNCS, vol. 520, pp. 211–220. Springer, Heidelberg (1991). doi:10.​1007/​3-540-54345-7_​64 CrossRef
104.
Huang, S., Aubanel, E., Bhavsar, V.C.: PaGrid: a mesh partitioner for computational grids. J. Grid Comput. 4(1), 71–88 (2006)CrossRef
105.
Hungershöfer, J., Wierum, J.-M.: On the quality of partitions based on space-filling curves. In: Sloot, P.M.A., Hoekstra, A.G., Tan, C.J.K., Dongarra, J.J. (eds.) ICCS 2002. LNCS, vol. 2331, pp. 36–45. Springer, Heidelberg (2002). doi:10.​1007/​3-540-47789-6_​4 CrossRef
106.
Hyafil, L., Rivest, R.: Graph partitioning and constructing optimal decision trees are polynomial complete problems. Technical report 33, IRIA - Laboratoire de Recherche en Informatique et Automatique (1973)
107.
Jeannot, E., Mercier, G., Tessier, F.: Process placement in multicore clusters: algorithmic issues and practical techniques. IEEE Trans. Parallel Distrib. Syst. PP(99), 1–1 (2013)
108.
109.
Junker, B., Schreiber, F.: Analysis of Biological Networks. Wiley, Hoboken (2008)CrossRef
110.
Kahng, A.B., Lienig, J., Markov, I.L., Hu, J.: VLSI Physical Design - From Graph Partitioning to Timing Closure. Springer, Heidelberg (2011)MATHCrossRef
111.
Karisch, S.E., Rendl, F., Clausen, J.: Solving graph bisection problems with semidefinite programming. INFORMS J. Comput. 12(3), 177–191 (2000)MathSciNetMATHCrossRef
112.
Karypis, G., Kumar, V.: Parallel multilevel \(k\)-way partitioning scheme for irregular graphs. In: ACM/IEEE Supercomputing 1996 (1996)
113.
Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20(1), 359–392 (1998)MathSciNetMATHCrossRef
114.
Karypis, G., Kumar, V.: Multilevel \(k\)-way partitioning scheme for irregular graphs. J. Parallel Distrib. Comput. 48(1), 96–129 (1998)MathSciNetMATHCrossRef
115.
Karypis, G., Kumar, V.: Multilevel \(k\)-way hypergraph partitioning. In: 36th ACM/IEEE Design Automation Conference, pp. 343–348. ACM (1999)
116.
Karypis, G., Kumar, V.: Parallel multilevel series \(k\)-way partitioning scheme for irregular graphs. SIAM Rev. 41(2), 278–300 (1999)MathSciNetMATHCrossRef
117.
Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49(1), 291–307 (1970)MATHCrossRef
118.
Kieritz, T., Luxen, D., Sanders, P., Vetter, C.: Distributed time-dependent contraction hierarchies. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 83–93. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-13193-6_​8 CrossRef
119.
120.
121.
Kirmani, S., Raghavan, P.: Scalable parallel graph partitioning. In: High Performance Computing, Networking, Storage and Analysis, SC 2013. ACM (2013)
122.
Korosec, P., Silc, J., Robic, B.: Solving the mesh-partitioning problem with an ant-colony algorithm. Parallel Comput. 30(5–6), 785–801 (2004)MATHCrossRef
123.
Kunegis, J.: KONECT - the Koblenz network collection. In: Web Observatory Workshop, pp. 1343–1350 (2013)
124.
Lafon, S., Lee, A.B.: Diffusion maps and coarse-graining: a unified framework for dimensionality reduction, graph partioning and data set parametrization. IEEE Trans. Pattern Anal. Mach. Intell. 28(9), 1393–1403 (2006)CrossRef
125.
Lanczos, C.: An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. J. Res. Natl Bur. Stand. 45(4), 255–282 (1950)MathSciNetCrossRef
126.
127.
Lang, K., Rao, S.: A flow-based method for improving the expansion or conductance of graph cuts. In: Bienstock, D., Nemhauser, G. (eds.) IPCO 2004. LNCS, vol. 3064, pp. 325–337. Springer, Heidelberg (2004). doi:10.​1007/​978-3-540-25960-2_​25 CrossRef
128.
Lasalle, D., Karypis, G.: Multi-threaded graph partitioning. In: 27th International Parallel and Distributed Processing Symposium (IPDPS), pp. 225–236 (2013)
129.
Lauther, U.: An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background. In: Münster GI-Days (2004)
130.
Leighton, F.T.: Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann Publishers, Burlington (1992)MATH
131.
132.
Li, H., Rosenwald, G., Jung, J., Liu, C.C.: Strategic power infrastructure defense. Proc. IEEE 93(5), 918–933 (2005)CrossRef
133.
Li, J., Liu, C.C.: Power system reconfiguration based on multilevel graph partitioning. In: PowerTech, pp. 1–5 (2009)
134.
135.
136.
Lovász, L.: Random walks on graphs: a survey. Comb. Paul Erdös is Eighty 2, 1–46 (1993)
137.
Low, Y., Gonzalez, J., Kyrola, A., Bickson, D., Guestrin, C., Hellerstein, J.M.: Distributed GraphLab: a framework for machine learning in the cloud. PVLDB 5(8), 716–727 (2012)
138.
139.
Malewicz, G., Austern, M.H., Bik, A.J.C., Dehnert, J.C., Horn, I., Leiser, N., Czajkowski, G.: Pregel: a system for large-scale graph processing. In: ACM SIGMOD International Conference on Management of Data (SIGMOD), pp. 135–146. ACM (2010)
140.
141.
Maue, J., Sanders, P., Matijevic, D.: Goal directed shortest path queries using precomputed cluster distances. ACM J. Exp. Algorithmics 14, 3.2:1–3.2:27 (2009)MathSciNetMATH
142.
143.
Meyerhenke, H., Monien, B., Sauerwald, T.: A new diffusion-based multilevel algorithm for computing graph partitions. J. Parallel Distrib. Comput. 69(9), 750–761 (2009)CrossRef
144.
Meyerhenke, H., Monien, B., Schamberger, S.: Accelerating shape optimizing load balancing for parallel FEM simulations by algebraic multigrid. In: 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS), p. 57 (CD) (2006)
145.
Meyerhenke, H., Sanders, P., Schulz, C.: Partitioning complex networks via size-constrained clustering. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 351–363. Springer, Heidelberg (2014). doi:10.​1007/​978-3-319-07959-2_​30
146.
Meyerhenke, H.: Disturbed diffusive processes for solving partitioning problems on graphs. Ph.D. thesis, Universität Paderborn (2008)
147.
Meyerhenke, H.: Shape optimizing load balancing for MPI-parallel adaptive numerical simulations. In: Bader et al. [13], pp. 67–82
148.
Meyerhenke, H., Monien, B., Schamberger, S.: Graph partitioning and disturbed diffusion. Parallel Comput. 35(10–11), 544–569 (2009)CrossRef
149.
Meyerhenke, H., Sanders, P., Schulz, C.: Parallel graph partitioning for complex networks. In: Proceeding of the 29th IEEE International Parallel & Distributed Processing Symposium, (IPDPS 2015) (2015 to appear). Preliminary version: http://​arxiv.​org/​abs/​1404.​4797
150.
Meyerhenke, H., Sauerwald, T.: Beyond good partition shapes: an analysis of diffusive graph partitioning. Algorithmica 64(3), 329–361 (2012)MathSciNetMATHCrossRef
151.
Meyerhenke, H., Schamberger, S.: Balancing parallel adaptive FEM computations by solving systems of linear equations. In: Cunha, J.C., Medeiros, P.D. (eds.) Euro-Par 2005. LNCS, vol. 3648, pp. 209–219. Springer, Heidelberg (2005). doi:10.​1007/​11549468_​26 CrossRef
152.
Miller, G., Teng, S.H., Vavasis, S.: A unified geometric approach to graph separators. In: 32nd Symposium on Foundations of Computer Science (FOCS), pp. 538–547 (1991)
153.
Möhring, R.H., Schilling, H., Schütz, B., Wagner, D., Willhalm, T.: Partitioning graphs to speedup Dijkstra’s algorithm. ACM J. Exp. Algorithmics 11, 1–29 (2006, 2007)
154.
155.
Monien, B., Schamberger, S.: Graph partitioning with the party library: helpful-sets in practice. In: 16th Symposium on Computer Architecture and High Performance Computing, pp. 198–205 (2004)
156.
Monien, B., Preis, R., Schamberger, S.: Approximation algorithms for multilevel graph partitioning. In: Gonzalez, T.F. (ed.) Handbook of Approximation Algorithms and Metaheuristics, chap. 60, pp. 60-1–60-15. Taylor & Francis, Abingdon (2007)
157.
158.
Newman, M.E.J.: Community detection and graph partitioning. CoRR abs/1305.4974 (2013)
159.
160.
Nishimura, J., Ugander, J.: Restreaming graph partitioning: simple versatile algorithms for advanced balancing. In: 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) (2013)
161.
162.
Papa, D.A., Markov, I.L.: Hypergraph partitioning and clustering. In: Gonzalez, T.F. (ed.) Handbook of Approximation Algorithms and Metaheuristics, chap. 61, pp. 61-1–61-19. CRC Press, Boca Raton (2007)
163.
164.
Pellegrini, F.: Static mapping by dual recursive bipartitioning of process and architecture graphs. In: Scalable High-Performance Computing Conference (SHPCC), pp. 486–493. IEEE, May 1994
165.
Pellegrini, F.: A parallelisable multi-level banded diffusion scheme for computing balanced partitions with smooth boundaries. In: Kermarrec, A.-M., Bougé, L., Priol, T. (eds.) Euro-Par 2007. LNCS, vol. 4641, pp. 195–204. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-74466-5_​22 CrossRef
166.
Pellegrini, F.: Scotch and libScotch 5.0 user’s guide. Technical report, LaBRI, Université Bordeaux I, December 2007
167.
Pellegrini, F.: Static mapping of process graphs. In: Bichot, C.E., Siarry, P. (eds.) Graph Partitioning, chap. 5, pp. 115–136. Wiley, Hoboken (2011)
168.
Pellegrini, F.: Scotch and PT-Scotch graph partitioning software: an overview. In: Naumann, U., Schenk, O. (eds.) Combinatorial Scientific Computing, pp. 373–406. CRC Press, Boca Raton (2012)CrossRef
169.
Peng, B., Zhang, L., Zhang, D.: A survey of graph theoretical approaches to image segmentation. Pattern Recognit. 46(3), 1020–1038 (2013)CrossRef
170.
Pettie, S., Sanders, P.: A simpler linear time \(2/3-\epsilon \) approximation for maximum weight matching. Inf. Process. Lett. 91(6), 271–276 (2004)MathSciNetMATHCrossRef
171.
Pilkington, J.R., Baden, S.B.: Partitioning with space-filling curves. Technical report CS94-349, UC San Diego, Department of Computer Science and Engineering (1994)
172.
Pothen, A., Simon, H.D., Liou, K.P.: Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl. 11(3), 430–452 (1990)MathSciNetMATHCrossRef
173.
Preis, R.: Linear time 1/2-approximation algorithm for maximum weighted matching in general graphs. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 259–269. Springer, Heidelberg (1999). doi:10.​1007/​3-540-49116-3_​24 CrossRef
174.
Raghavan, U.N., Albert, R., Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E 76(3) (2007)
175.
Rolland, E., Pirkul, H., Glover, F.: Tabu search for graph partitioning. Ann. Oper. Res. 63(2), 209–232 (1996)MATHCrossRef
176.
Ron, D., Wishko-Stern, S., Brandt, A.: An algebraic multigrid based algorithm for bisectioning general graphs. Technical report MCS05-01, Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science (2005)
177.
Ron, D., Safro, I., Brandt, A.: A fast multigrid algorithm for energy minimization under planar density constraints. Multiscale Model. Simul. 8(5), 1599–1620 (2010)MathSciNetMATHCrossRef
178.
Ron, D., Safro, I., Brandt, A.: Relaxation-based coarsening and multiscale graph organization. Multiscale Model. Simul. 9(1), 407–423 (2011)MathSciNetMATHCrossRef
179.
Safro, I., Sanders, P., Schulz, C.: Advanced coarsening schemes for graph partitioning. In: Klasing, R. (ed.) SEA 2012. LNCS, vol. 7276, pp. 369–380. Springer, Heidelberg (2012)CrossRef
180.
Safro, I., Temkin, B.: Multiscale approach for the network compression-friendly ordering. J. Discret. Algorithms 9(2), 190–202 (2011)MathSciNetMATHCrossRef
181.
182.
Sanchis, L.A.: Multiple-way network partitioning. IEEE Trans. Comput. 38(1), 62–81 (1989)MATHCrossRef
183.
Sanders, P., Schulz, C.: Engineering multilevel graph partitioning algorithms. In: Demetrescu, C., Halldórsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 469–480. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-23719-5_​40 CrossRef
184.
Sanders, P., Schulz, C.: Distributed evolutionary graph partitioning. In: 12th Workshop on Algorithm Engineering and Experimentation (ALENEX), pp. 16–29 (2012)
185.
Sanders, P., Schulz, C.: High quality graph partitioning. In: Bader et al. [13], pp. 19–36
186.
Sanders, P., Schulz, C.: Think locally, act globally: highly balanced graph partitioning. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 164–175. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-38527-8_​16 CrossRef
187.
188.
189.
Schamberger, S.: On partitioning FEM graphs using diffusion. In: HPGC Workshop of the 18th International Parallel and Distributed Processing Symposium (IPDPS 2004). IEEE Computer Society (2004)
190.
Schamberger, S., Wierum, J.M.: A locality preserving graph ordering approach for implicit partitioning: graph-filling curves. In: 17th International Conference on Parallel and Distributed Computing Systems (PDCS), ISCA, pp. 51–57 (2004)
191.
Schloegel, K., Karypis, G., Kumar, V.: Graph partitioning for high-performance scientific simulations. In: Dongarra, J., Foster, I., Fox, G., Gropp, W., Kennedy, K., Torczon, L., White, A. (eds.) Sourcebook of parallel computing, pp. 491–541. Morgan Kaufmann Publishers, Burlington (2003)
192.
Schloegel, K., Karypis, G., Kumar, V.: Multilevel diffusion schemes for repartitioning of adaptive meshes. J. Parallel Distrib. Comput. 47(2), 109–124 (1997)MATHCrossRef
193.
Schloegel, K., Karypis, G., Kumar, V.: A unified algorithm for load-balancing adaptive scientific simulations. In: Supercomputing 2000, p. 59 (CD). IEEE Computer Society (2000)
194.
Schloegel, K., Karypis, G., Kumar, V.: Parallel static and dynamic multi-constraint graph partitioning. Concurr. Comput.: Pract. Exp. 14(3), 219–240 (2002)MATHCrossRef
195.
Schulz, C.: High quality graph partititioning. Ph.D. thesis. epubli GmbH (2013)
196.
Schulz, F., Wagner, D., Zaroliagis, C.: Using multi-level graphs for timetable information in railway systems. In: Mount, D.M., Stein, C. (eds.) ALENEX 2002. LNCS, vol. 2409, pp. 43–59. Springer, Heidelberg (2002). doi:10.​1007/​3-540-45643-0_​4 CrossRef
197.
Sellmann, M., Sensen, N., Timajev, L.: Multicommodity flow approximation used for exact graph partitioning. In: Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol. 2832, pp. 752–764. Springer, Heidelberg (2003). doi:10.​1007/​978-3-540-39658-1_​67 CrossRef
198.
Sensen, N.: Lower bounds and exact algorithms for the graph partitioning problem using multicommodity flows. In: Heide, F.M. (ed.) ESA 2001. LNCS, vol. 2161, pp. 391–403. Springer, Heidelberg (2001). doi:10.​1007/​3-540-44676-1_​33 CrossRef
199.
Shalf, J., Dosanjh, S., Morrison, J.: Exascale computing technology challenges. In: Palma, J.M.L.M., Daydé, M., Marques, O., Lopes, J.C. (eds.) VECPAR 2010. LNCS, vol. 6449, pp. 1–25. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-19328-6_​1 CrossRef
200.
Simon, H.D.: Partitioning of unstructured problems for parallel processing. Comput. Syst. Eng. 2(2), 135–148 (1991)CrossRef
201.
202.
Soper, A.J., Walshaw, C., Cross, M.: A combined evolutionary search and multilevel optimisation approach to graph-partitioning. J. Glob. Optim. 29(2), 225–241 (2004)MathSciNetMATHCrossRef
203.
Stanton, I., Kliot, G.: Streaming graph partitioning for large distributed graphs. In: 18th ACM SIGKDD International Conference on Knowledge discovery and data mining (KDD), pp. 1222–1230. ACM (2012)
204.
205.
Sui, X., Nguyen, D., Burtscher, M., Pingali, K.: Parallel graph partitioning on multicore architectures. In: Cooper, K., Mellor-Crummey, J., Sarkar, V. (eds.) LCPC 2010. LNCS, vol. 6548, pp. 246–260. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-19595-2_​17 CrossRef
206.
Tang, L., Liu, H., Zhang, J., Nazeri, Z.: Community evolution in dynamic multi-mode networks. In: 14th ACM SIGKDD International Conference on Knowledge discovery and data mining (KDD), pp. 677–685. ACM (2008)
207.
208.
Trifunović, A., Knottenbelt, W.J.: Parallel multilevel algorithms for hypergraph partitioning. J. Parallel Distrib. Comput. 68(5), 563–581 (2008)MATHCrossRef
209.
Tsourakakis, C.E., Gkantsidis, C., Radunovic, B., Vojnovic, M.: Fennel: streaming graph partitioning for massive scale graphs. Technical report MSR-TR-2012-113, Microsoft Research (2000)
210.
211.
Wagner, D., Wagner, F.: Between min cut and graph bisection. In: Borzyszkowski, A.M., Sokołowski, S. (eds.) MFCS 1993. LNCS, vol. 711, pp. 744–750. Springer, Heidelberg (1993). doi:10.​1007/​3-540-57182-5_​65 CrossRef
212.
213.
Walshaw, C., Cross, M.: Mesh partitioning: a multilevel balancing and refinement algorithm. SIAM J. Sci. Comput. 22(1), 63–80 (2000)MathSciNetMATHCrossRef
214.
Walshaw, C., Cross, M.: Parallel mesh partitioning on distributed memory systems. In: Topping, B. (ed.) Computational Mechanics Using High Performance Computing, pp. 59–78. Saxe-Coburg Publications, Stirling (2002). Invited chapterCrossRef
215.
Walshaw, C., Cross, M.: JOSTLE: parallel multilevel graph-partitioning software - an overview. In: Mesh Partitioning Techniques and Domain Decomposition Techniques, pp. 27–58. Civil-Comp Ltd. (2007)
216.
Walshaw, C., Cross, M., Everett, M.G.: A localized algorithm for optimizing unstructured mesh partitions. J. High Perform. Comput. Appl. 9(4), 280–295 (1995)CrossRef
217.
Walshaw, C.: Variable partition inertia: graph repartitioning and load balancing for adaptive meshes. In: Parashar, M., Li, X. (eds.) Advanced Computational Infrastructures for Parallel and Distributed Adaptive Applications, pp. 357–380. Wiley Online Library, Hoboken (2010)
218.
Walshaw, C., Cross, M.: Multilevel mesh partitioning for heterogeneous communication networks. Future Gener. Comp. Syst. 17(5), 601–623 (2001)CrossRef
219.
Walshaw, C., Cross, M., Everett, M.G.: Dynamic load-balancing for parallel adaptive unstructured meshes. In: Proceedings of the 8th SIAM Conference on Parallel Processing for Scientific Computing (PPSC 1997) (1997)
220.
221.
Williams, R.D.: Performance of dynamic load balancing algorithms for unstructured mesh calculations. Concurr.: Pract. Exp. 3(5), 457–481 (1991)CrossRef
222.
Zhou, M., Sahni, O., et al.: Controlling unstructured mesh partitions for massively parallel simulations. SIAM J. Sci. Comput. 32(6), 3201–3227 (2010)MathSciNetMATHCrossRef
223.
Zumbusch, G.: Parallel Multilevel Methods: Adaptive Mesh Refinement and Loadbalancing. Teubner, Stuttgart (2003)MATHCrossRef
Metadaten
Titel
Recent Advances in Graph Partitioning
verfasst von
Aydın Buluç
Henning Meyerhenke
Ilya Safro
Peter Sanders
Christian Schulz
Copyright-Jahr
2016
Buch
Algorithm Engineering

Print ISBN: 978-3-319-49486-9

Electronic ISBN: 978-3-319-49487-6

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-49487-6_4