{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T09:53:47Z","timestamp":1667210027134},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,8,22]],"date-time":"2018-08-22T00:00:00Z","timestamp":1534896000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["New Gener. Comput."],"published-print":{"date-parts":[[2018,10]]},"DOI":"10.1007\/s00354-018-0042-6","type":"journal-article","created":{"date-parts":[[2018,8,22]],"date-time":"2018-08-22T11:18:51Z","timestamp":1534936731000},"page":"419-449","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On Implementing the Push-Relabel Algorithm on Top of Pregel"],"prefix":"10.1007","volume":"36","author":[{"given":"Shigeyuki","family":"Sato","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,8,22]]},"reference":[{"issue":"5","key":"42_CR1","doi-asserted-by":"publisher","first-page":"906","DOI":"10.1137\/S0097539791199334","volume":"23","author":"RK Ahuja","year":"1994","unstructured":"Ahuja, R.K., Orlin, J.B., Stein, C., Tarjan, R.E.: Improved algorithms for bipartite network flow. SIAM J. Comput. 23(5), 906\u2013933 (1994)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"42_CR2","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1145\/161541.161736","volume":"11","author":"TE Anderson","year":"1993","unstructured":"Anderson, T.E., Owicki, S.S., Saxe, J.B., Thacker, C.P.: High speed switch scheduling for local area networks. ACM Trans. Comput. Syst. 11(4), 319\u2013352 (1993)","journal-title":"ACM Trans. Comput. Syst."},{"issue":"3","key":"42_CR3","doi-asserted-by":"publisher","first-page":"1189","DOI":"10.1007\/s10586-015-0472-6","volume":"18","author":"O Batarfi","year":"2015","unstructured":"Batarfi, O., Shawi, R.E., Fayoumi, A.G., Nouri, R., Beheshti, S., Barnawi, A., Sakr, S.: Large scale graph processing systems: survey and an experimental evaluation. Clust. Comput. 18(3), 1189\u20131213 (2015)","journal-title":"Clust. Comput."},{"key":"42_CR4","doi-asserted-by":"crossref","unstructured":"Baumstark, N., Blelloch, G., Shun, J.: Efficient implementation of a synchronous parallel push\u2013relabel algorithm. In: Proceedings of 23rd Annual European Symposium on Algorithms (ESA \u201915), pp. 106\u2013117. Springer (2015)","DOI":"10.1007\/978-3-662-48350-3_10"},{"key":"42_CR5","doi-asserted-by":"crossref","unstructured":"Chen, R., Shi, J., Chen, Y., Chen, H.: PowerLyra: differentiated graph computation and partitioning on skewed graphs. In: Proceedings of 20th European Conference on Computer Systems (EuroSys \u201915), pp. 1:1\u20131:15. ACM (2015)","DOI":"10.1145\/2741948.2741970"},{"issue":"4","key":"42_CR6","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/PL00009180","volume":"19","author":"BV Cherkassky","year":"1997","unstructured":"Cherkassky, B.V., Goldberg, A.V.: On implementing the push\u2013relabel method for the maximum flow problem. Algorithmica 19(4), 390\u2013410 (1997)","journal-title":"Algorithmica"},{"issue":"12","key":"42_CR7","first-page":"1804","volume":"8","author":"A Ching","year":"2015","unstructured":"Ching, A., Edunov, S., Kabiljo, M., Logothetis, D., Muthukrishnan, S.: One trillion edges: graph processing at Facebook-scale. PVLDB 8(12), 1804\u20131815 (2015)","journal-title":"PVLDB"},{"key":"42_CR8","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/1327452.1327492","volume":"51","author":"J Dean","year":"2008","unstructured":"Dean, J., Ghemawat, S.: MapReduce: simplified data processing on large clusters. Commun. ACM 51, 107\u2013113 (2008)","journal-title":"Commun. ACM"},{"key":"42_CR9","doi-asserted-by":"crossref","unstructured":"Delong, A., Boykov, Y.: A scalable graph-cut algorithm for N-D Grids. In: Proceedings of 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR \u201908). IEEE (2008)","DOI":"10.1109\/CVPR.2008.4587464"},{"key":"42_CR10","unstructured":"Doekemeijer, N., Varbanescu, A.L.: A Survey of Parallel Graph Processing Frameworks. Tech. Rep. PDS-2014-003, Delft University of Technology (2014)"},{"key":"42_CR11","unstructured":"Goldberg, A.V.: Efficient graph algorithms for sequential and parallel computers. Ph.D. Thesis, Massachusetts Institute of Technology (1987)"},{"key":"42_CR12","doi-asserted-by":"crossref","unstructured":"Goldberg, A.V.: Two-level push\u2013relabel algorithm for the maximum flow problem. In: Proceedings of 5th International Conference Algorithmic Aspects in Information and Management (AAAI \u201909), pp. 212\u2013225. Springer (2009)","DOI":"10.1007\/978-3-642-02158-9_19"},{"issue":"4","key":"42_CR13","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"AV Goldberg","year":"1988","unstructured":"Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum-flow problem. J. ACM 35(4), 921\u2013940 (1988)","journal-title":"J. ACM"},{"key":"42_CR14","unstructured":"Gonzalez, J.E., Low, Y., Gu, H., Bickson, D., Guestrin, C.: PowerGraph: distributed graph-parallel computation on natural graphs. In: Proceedings of 10th USENIX Conference on Operating Systems Design and Implementation (OSDI \u201910), pp. 17\u201330. USENIX (2012)"},{"key":"42_CR15","unstructured":"Gonzalez, J.E., Xin, R.S., Dave, A., Crankshaw, D., Franklin, M.J., Stoica, I.: GraphX: graph processing in a distributed dataflow framework. In: Proceedings of 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI \u201914), pp. 599\u2013613. USENIX (2014)"},{"key":"42_CR16","doi-asserted-by":"crossref","unstructured":"Guo, Y., Biczak, M., Varbanescu, A.L., Iosup, A., Martella, C., Willke, T.L.: How well do graph-processing platforms perform? An empirical performance evaluation and analysis. In: Proceedings of 28th International Parallel and Distributed Processing Symposium (IPDPS \u201914), pp. 395\u2013404. IEEE (2014)","DOI":"10.1109\/IPDPS.2014.49"},{"key":"42_CR17","doi-asserted-by":"crossref","unstructured":"Halim, F., Yap, R.H.C., Wu, Y.: A MapReduce-based maximum-flow algorithm for large small-world network graphs. In: Proceedings of 2011 International Conference on Distributed Computing Systems (ICDCS \u201911), pp. 192\u2013202. IEEE (2011)","DOI":"10.1109\/ICDCS.2011.62"},{"issue":"13","key":"42_CR18","first-page":"1317","volume":"9","author":"A Iosup","year":"2016","unstructured":"Iosup, A., Hegeman, T., Ngai, W.L., Heldens, S., Prat-P\u00e9rez, A., Manhardt, T., Chafi, H., Capota, M., Sundaram, N., Anderson, M.J., Tanase, I.G., Xia, Y., Nai, L., Boncz, P.A.: LDBC graphalytics: a benchmark for large-scale graph analysis on parallel and distributed platforms. PVLDB 9(13), 1317\u20131328 (2016)","journal-title":"PVLDB"},{"issue":"2","key":"42_CR19","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1007\/s11227-014-1314-7","volume":"71","author":"J Jiang","year":"2015","unstructured":"Jiang, J., Wu, L.: Two-stage distributed parallel algorithm with message passing interface for maximum flow problem. J. Supercomput. 71(2), 629\u2013647 (2015)","journal-title":"J. Supercomput."},{"issue":"2","key":"42_CR20","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1109\/TKDE.2017.2762294","volume":"30","author":"V Kalavri","year":"2018","unstructured":"Kalavri, V., Vlassov, V., Haridi, S.: High-level programming abstractions for distributed graph processing. IEEE Trans. Knowl. Data Eng. 30(2), 305\u2013324 (2018)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"42_CR21","doi-asserted-by":"crossref","unstructured":"Kulkarni, M., Burtscher, M., Inkulu, R., Pingali, K., Cascaval, C.: How much parallelism is there in irregular applications? In: Proceedings of 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP \u201909), pp. 3\u201314. ACM (2009)","DOI":"10.1145\/1504176.1504181"},{"key":"42_CR22","unstructured":"Langewisch, R.P.: A performance study of an implementation of the push-relabel maximum flow algorithm in apache spark\u2019s graphx. Master\u2019s Thesis, Colorado School of Mines (2015)"},{"issue":"3","key":"42_CR23","first-page":"281","volume":"8","author":"Y Lu","year":"2014","unstructured":"Lu, Y., Cheng, J., Yan, D., Wu, H.: Large-scale distributed graph computing systems: an experimental evaluation. PVLDB 8(3), 281\u2013292 (2014)","journal-title":"PVLDB"},{"key":"42_CR24","doi-asserted-by":"crossref","unstructured":"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: Proceedings of 2010 ACM SIGMOD International Conference on Management of Data (SIGMOD \u201910), pp. 135\u2013146. ACM (2010)","DOI":"10.1145\/1807167.1807184"},{"issue":"2","key":"42_CR25","doi-asserted-by":"publisher","first-page":"25:1","DOI":"10.1145\/2818185","volume":"48","author":"RR McCune","year":"2015","unstructured":"McCune, R.R., Weninger, T., Madey, G.: Thinking like a vertex: a survey of vertex-centric frameworks for large-scale distributed graph processing. ACM Comput. Surv. 48(2), 25:1\u201325:39 (2015)","journal-title":"ACM Comput. Surv."},{"issue":"3","key":"42_CR26","first-page":"3.5:3.1","volume":"16","author":"CS Negruseri","year":"2011","unstructured":"Negruseri, C.S., Pacsosi, M.B., Stanley, B., Stein, C., Strat, C.G.: Solving maximum flow problems on real-world bipartite graphs. J. Exp. Algorithmics 16(3), 3.5:3.1\u20133.5:3.25 (2011)","journal-title":"J. Exp. Algorithmics"},{"key":"42_CR27","doi-asserted-by":"crossref","unstructured":"Petroni, F., Querzoni, L., Daudjee, K., Kamali, S., Iacoboni, G.: HDRF: stream-based partitioning for power-law graphs. In: Proceedings of 24th ACM International on Conference on Information and Knowledge Management (CIKM \u201915), pp. 243\u2013252. ACM (2015)","DOI":"10.1145\/2806416.2806424"},{"issue":"2","key":"42_CR28","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s00778-015-0405-2","volume":"25","author":"A Quamar","year":"2016","unstructured":"Quamar, A., Deshpande, A., Lin, J.J.: NScale: neighborhood-centric large-scale graph analytics in the cloud. VLDB J. 25(2), 125\u2013150 (2016)","journal-title":"VLDB J."},{"key":"42_CR29","doi-asserted-by":"crossref","unstructured":"Roy, A., Mihailovic, I., Zwaenepoel, W.: X-Stream: edge-centric graph processing using streaming partitions. In: Proceedings of ACM SIGOPS 24th Symposium on Operating Systems Principles (SOSP \u201913), pp. 472\u2013488. ACM (2013)","DOI":"10.1145\/2517349.2522740"},{"issue":"7","key":"42_CR30","first-page":"577","volume":"7","author":"S Salihoglu","year":"2014","unstructured":"Salihoglu, S., Widom, J.: Optimizing graph algorithms on pregel-like systems. PVLDB 7(7), 577\u2013588 (2014)","journal-title":"PVLDB"},{"key":"42_CR31","doi-asserted-by":"crossref","unstructured":"Satish, N., Sundaram, N., Patwary, M.M.A., Seo, J., Park, J., Hassaan, M.A., Sengupta, S., Yin, Z., Dubey, P.: Navigating the maze of graph analytics frameworks using massive graph datasets. In: Proceedings of 2014 ACM SIGMOD International Conference on Management of Data (SIGMOD \u201914), pp. 979\u2013990. ACM (2014)","DOI":"10.1145\/2588555.2610518"},{"issue":"3","key":"42_CR32","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/s11263-012-0571-2","volume":"104","author":"A Shekhovtsov","year":"2013","unstructured":"Shekhovtsov, A., Hlav\u00e1\u010d, V.: A distributed mincut\/maxflow algorithm combining path augmentation and push-relabel. Int. J. Comput. Vis. 104(3), 315\u2013342 (2013)","journal-title":"Int. J. Comput. Vis."},{"issue":"3","key":"42_CR33","first-page":"193","volume":"7","author":"Y Tian","year":"2013","unstructured":"Tian, Y., Balmin, A., Corsten, S.A., Tatikonda, S., McPherson, J.: From \u201cThink Like a Vertex\u201d to \u201cThink Like a Graph\u201d. PVLDB 7(3), 193\u2013204 (2013)","journal-title":"PVLDB"},{"issue":"8","key":"42_CR34","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"LG Valiant","year":"1990","unstructured":"Valiant, L.G.: A bridging model for parallel computation. Commun. ACM 33(8), 103\u2013111 (1990)","journal-title":"Commun. ACM"},{"key":"42_CR35","unstructured":"Xie, C., Yan, L., Li, W.J., Zhang, Z.: Distributed power-law graph computing: theoretical and empirical analysis. In: Proceedings of 27th International Conference on Neural Information Processing Systems (NIPS \u201914), pp. 1673\u20131681. MIT Press (2014)"},{"issue":"13","key":"42_CR36","first-page":"1981","volume":"7","author":"D Yan","year":"2014","unstructured":"Yan, D., Cheng, J., Lu, Y., Ng, W.: Blogel: a block-centric framework for distributed computation on real-world graphs. PVLDB 7(13), 1981\u20131992 (2014)","journal-title":"PVLDB"},{"key":"42_CR37","doi-asserted-by":"crossref","unstructured":"Yan, D., Cheng, J., Lu, Y., Ng, W.: Effective Techniques for Message Reduction and Load Balancing in Distributed Graph Computation. In: Proceedings of 24th International Conference on World Wide Web (WWW \u201915), pp. 1307\u20131317. ACM (2015)","DOI":"10.1145\/2736277.2741096"},{"issue":"11","key":"42_CR38","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1145\/2934664","volume":"59","author":"M Zaharia","year":"2016","unstructured":"Zaharia, M., Xin, R.S., Wendell, P., Das, T., Armbrust, M., Dave, A., Meng, X., Rosen, J., Venkataraman, S., Franklin, M.J., Ghodsi, A., Gonzalez, J., Shenker, S., Stoica, I.: Apache spark: a unified engine for big data processing. Commun. ACM 59(11), 56\u201365 (2016)","journal-title":"Commun. ACM"}],"container-title":["New Generation Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00354-018-0042-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00354-018-0042-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00354-018-0042-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,21]],"date-time":"2019-08-21T19:07:39Z","timestamp":1566414459000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00354-018-0042-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,22]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,10]]}},"alternative-id":["42"],"URL":"https:\/\/doi.org\/10.1007\/s00354-018-0042-6","relation":{},"ISSN":["0288-3635","1882-7055"],"issn-type":[{"value":"0288-3635","type":"print"},{"value":"1882-7055","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,22]]},"assertion":[{"value":"1 November 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 July 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 August 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}