{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T15:50:46Z","timestamp":1759333846698,"version":"build-2065373602"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783032067500"},{"type":"electronic","value":"9783032067517"}],"license":[{"start":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T00:00:00Z","timestamp":1759276800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T00:00:00Z","timestamp":1759276800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-06751-7_3","type":"book-chapter","created":{"date-parts":[[2025,9,30]],"date-time":"2025-09-30T04:29:23Z","timestamp":1759206563000},"page":"33-48","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Composable Parallelism in\u00a0Graph Processing"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0343-3859","authenticated-orcid":false,"given":"Vladimir","family":"Bakhtin","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7603-4026","authenticated-orcid":false,"given":"Nikita","family":"Kataev","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1384-7484","authenticated-orcid":false,"given":"Alexander","family":"Kolganov","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6319-5090","authenticated-orcid":false,"given":"Dmitry","family":"Zakharov","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2971-4248","authenticated-orcid":false,"given":"Alexander","family":"Smirnov","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0004-9276-2172","authenticated-orcid":false,"given":"Anton","family":"Malahov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,10,1]]},"reference":[{"key":"3_CR1","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/BF02592101","volume":"73","author":"BV Cherkassky","year":"1996","unstructured":"Cherkassky, B.V., Goldberg, A.V., Radzik, T.: Shortest paths algorithms: theory and experimental evaluation. Math. Program. 73, 129\u2013174 (1996). https:\/\/doi.org\/10.1007\/BF02592101","journal-title":"Math. Program."},{"key":"3_CR2","unstructured":"Moore, E.F.: The shortest path through a maze. In: International Symposium on Theory of Switching, pp. 285\u2013292 (1959)"},{"issue":"6","key":"3_CR3","doi-asserted-by":"publisher","first-page":"1028","DOI":"10.1145\/355541.355562","volume":"47","author":"BA Chazelle","year":"2000","unstructured":"Chazelle, B.A.: Minimum spanning tree algorithm with inverse-ackermann type complexity. J. ACM 47(6), 1028\u20131047 (2000)","journal-title":"J. ACM"},{"key":"3_CR4","doi-asserted-by":"publisher","unstructured":"Kolganov, A.S.: Parallel implementation of minimum spanning tree algorithm on CPU and GPU. Comput. Math. Softw. Eng. 5(2), 5\u201319 (2016). https:\/\/doi.org\/10.14529\/cmse160301","DOI":"10.14529\/cmse160301"},{"key":"3_CR5","unstructured":"Graph500. http:\/\/graph500.org\/. Accessed 14 July 2025"},{"key":"3_CR6","unstructured":"Green Graph500. https:\/\/graph500.org\/?page_id=446. Accessed 14 July 2025"},{"key":"3_CR7","unstructured":"Top500. https:\/\/www.top500.org\/. Accessed 14 July 2025"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Fiksman, E., Malakhov, A.: Efficient nested parallelism on large-scale systems (chapter 18). In: High Performance Parallelism Pearls: Multicore and Many-core Programming Approaches by Reinders, James, Jeffers, James, chapter 18, pp. 307\u2013318 (2014). Morgan Kaufmann","DOI":"10.1016\/B978-0-12-802118-7.00018-2"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"Malakhov, A.A., Liu, D., Gorshkov, A.V., Wilmarth, T.: Composable multi-threading and multi-processing for numeric libraries. In: SciPy, pp. 18\u201324. https:\/\/proceedings.scipy.org\/articles\/Majora-4af1f417-003.pdf","DOI":"10.25080\/Majora-4af1f417-003"},{"key":"3_CR10","doi-asserted-by":"publisher","unstructured":"Malakhov, A.: Composable multi-threading for python libraries. In: Proceedings of the 15th Python in Science Conference, pp. 15\u201319 (2016). https:\/\/doi.org\/10.25080\/Majora-629e541a-002","DOI":"10.25080\/Majora-629e541a-002"},{"key":"3_CR11","unstructured":"Malakhov, A.: Fusing Efficient Parallel For Loops with a Composable Task Scheduler, Hydra Conference, 2022"},{"key":"3_CR12","doi-asserted-by":"publisher","unstructured":"Bakhtin, V., Kataev, N., Kolganov, A., Zakharov, D., Smirnov, A., Kocharmin, M.: A study of a composable approach to parallel programming for many-core multiprocessors. In: Voevodin, V., Antonov, A., Nikitenko, D. (eds.) Supercomputing. RuSCDays 2024. LNCS, vol. 15406, pp. 285\u2013299. Springer, Cham (2025). https:\/\/doi.org\/10.1007\/978-3-031-78459-0_21","DOI":"10.1007\/978-3-031-78459-0_21"},{"key":"3_CR13","doi-asserted-by":"publisher","unstructured":"Bakhtin, V.A., Kataev, N.A., Kolganov, A.S., Smirnov, A.A., Zaharov, D.A.: Exploring composable parallelism in computational modelling. Math. Models Comput. Simul. 16(suppl 2), 216\u2013224 (2024). US: Pleiades Publishing, Ltd. https:\/\/doi.org\/10.1134\/S2070048224700923","DOI":"10.1134\/S2070048224700923"},{"key":"3_CR14","doi-asserted-by":"publisher","unstructured":"Iwasaki, S., Amer, A., Taura. K., Seo, S., Balaji, P.: BOLT: optimizing OpenMP parallel regions with user-level threads. In: Proceedings of the 28th International Conference on Parallel Architectures and Compilation Techniques (PACT \u201919), Sept. 2019 , pp. 29\u201342 (2019). https:\/\/doi.org\/10.1109\/PACT.2019.00011","DOI":"10.1109\/PACT.2019.00011"},{"key":"3_CR15","doi-asserted-by":"publisher","unstructured":"Seo, S., Amer, A., Balaji, P., et al.: Argobots: a lightweight low-level threading and tasking framework. IEEE Trans. Parallel Distrib. Syst. (TPDS) (2017). https:\/\/doi.org\/10.1109\/TPDS.2017.2766062","DOI":"10.1109\/TPDS.2017.2766062"},{"key":"3_CR16","unstructured":"oneTBB. https:\/\/github.com\/oneapi-src\/oneTBB. Accessed 14 July 2025"},{"key":"3_CR17","unstructured":"Taskflow. A General-purpose Task-parallel Programming System. https:\/\/taskflow.github.io\/. Accessed 14 July 2025"},{"key":"3_CR18","unstructured":"The LLVM Compiler Infrastructure. https:\/\/llvm.org\/. Accessed 14 July 2025"},{"key":"3_CR19","volume-title":"Introduction to Algorithms","author":"T Cormen","year":"1990","unstructured":"Cormen, T., Leiserson, C., Rivest, R.: Introduction to Algorithms. MIT Press, Cambridge (1990)"},{"issue":"2","key":"3_CR20","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/3-540-36478-1_4","volume":"19","author":"J Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19(2), 248\u2013264 (1972). https:\/\/doi.org\/10.1007\/3-540-36478-1_4","journal-title":"J. ACM"},{"key":"3_CR21","doi-asserted-by":"publisher","unstructured":"Brandes, U.: A faster algorithm for betweenness centrality. J. Math. Sociol. 25(2), 163\u2013177 (2001).https:\/\/doi.org\/10.1080\/0022250X.2001.9990249","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"3_CR22","doi-asserted-by":"publisher","unstructured":"Frasca, M., Madduri, K., Raghavan, P.: NUMA-aware graph mining techniques for performance and energy efficiency. In: Proceedings of the ACM\/IEEE Int. Conference on High Performance Computing, Networking, Storage and Analysis (SC 2012), pp. 1\u201311. IEEE Computer Society (2012). https:\/\/doi.org\/10.1109\/SC.2012.81","DOI":"10.1109\/SC.2012.81"},{"key":"3_CR23","doi-asserted-by":"publisher","first-page":"7821","DOI":"10.1073\/pnas.122653799","volume":"99","author":"M Girvan","year":"2002","unstructured":"Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. U.S.A. 99, 7821\u20137826 (2002). https:\/\/doi.org\/10.1073\/pnas.122653799","journal-title":"Proc. Natl. Acad. Sci. U.S.A."},{"key":"3_CR24","doi-asserted-by":"publisher","unstructured":"Bader, D.A., Madduri, K.: Designing multithreaded algorithms for breadth-first search and st-connectivity on the Cray MTA-2. In: ICPP, pp. 523\u2013530 (2006). https:\/\/doi.org\/10.1109\/ICPP.2006.34","DOI":"10.1109\/ICPP.2006.34"},{"key":"3_CR25","unstructured":"Korf, R.E., Schultze, P.: Large-scale parallel breadth-first search. In: AAAI, pp. 1380\u20131385 (2005)"},{"key":"3_CR26","doi-asserted-by":"publisher","unstructured":"Yoo, A., Chow, E., Henderson, K., McLendon, W., Hendrickson, B., Catalyurek, U.: A scalable distributed parallel breadth-first search algorithm on BlueGene\/L. In: SC \u201905, p. 25 (2005). https:\/\/doi.org\/10.1109\/SC.2005.4","DOI":"10.1109\/SC.2005.4"},{"key":"3_CR27","unstructured":"Zhang, Y.,Hansen, E.A.: Parallel breadth-first heuristic search on a shared-memory architecture. In: AAAI Workshop on Heuristic Search, Memory-Based Heuristics and Their Applications (2006)"},{"key":"3_CR28","doi-asserted-by":"publisher","unstructured":"Yasui, Y., Fujisawa, K., Sato, Y.: Fast and energy-efficient breadth-first search on a single NUMA system. In: Kunkel J.M., Ludwig T., Meuer H.W. (eds.) Supercomputing. ISC 2014. LNCS, vol. 8488, pp. 365\u2013381. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-07518-1_23","DOI":"10.1007\/978-3-319-07518-1_23"},{"key":"3_CR29","doi-asserted-by":"publisher","unstructured":"Hiragushi, T., Takahashi, D.: Efficient hybrid breadth-first search on GPUs. In: Aversa R., Ko\u0142odziej J., Zhang J., Amato F., Fortino G. (eds.) Algorithms and Architectures for Parallel Processing. ICA3PP 2013. LNCS, vol. 8286, pp. 40\u201350. Springer, Cham (2013). https:\/\/doi.org\/10.1007\/978-3-319-03889-6_5","DOI":"10.1007\/978-3-319-03889-6_5"},{"key":"3_CR30","doi-asserted-by":"publisher","unstructured":"Merrill, D., Garland, M., Grimshaw, A.: Scalable GPU graph traversal. In: Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2012), pp. 117\u2013128 (2012). https:\/\/doi.org\/10.1145\/2370036.2145832","DOI":"10.1145\/2370036.2145832"},{"key":"3_CR31","doi-asserted-by":"publisher","unstructured":"Chakrabarti, D., Zhan, Y., Faloutsos, C.: R-MAT: a recursive model for graph mining. In: Proceedings of 4th International Conference on Data Mining, pp. 442\u2013446 (2004). https:\/\/doi.org\/10.1137\/1.9781611972740.43","DOI":"10.1137\/1.9781611972740.43"},{"key":"3_CR32","doi-asserted-by":"crossref","unstructured":"Pissanetzky, S.: Pissanetzky, S.: Sparse Matrix Technology. Academic Press, Cambridge (1984)","DOI":"10.1016\/B978-0-12-557580-5.50012-0"},{"key":"3_CR33","unstructured":"Miniconda. https:\/\/docs.anaconda.com\/free\/miniconda\/index.html. Accessed 14 July 2025"}],"container-title":["Lecture Notes in Computer Science","Parallel Computing Technologies"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-06751-7_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,30]],"date-time":"2025-09-30T04:29:27Z","timestamp":1759206567000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-06751-7_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,1]]},"ISBN":["9783032067500","9783032067517"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-06751-7_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025,10,1]]},"assertion":[{"value":"1 October 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"PaCT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Parallel Computing Technologies","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Almaty","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Kazakhstan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 October 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 October 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"pact2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ssd.sscc.ru\/conference\/pact2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}