{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T14:56:34Z","timestamp":1743087394485,"version":"3.40.3"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031304477"},{"type":"electronic","value":"9783031304484"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[[2023]]},"DOI":"10.1007\/978-3-031-30448-4_8","type":"book-chapter","created":{"date-parts":[[2023,4,24]],"date-time":"2023-04-24T20:29:36Z","timestamp":1682368176000},"page":"97-111","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Maximum Flows in\u00a0Parametric Graph Templates"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3657-6568","authenticated-orcid":false,"given":"Tal","family":"Ben-Nun","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5975-4526","authenticated-orcid":false,"given":"Lukas","family":"Gianinazzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1333-9797","authenticated-orcid":false,"given":"Torsten","family":"Hoefler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yishai","family":"Oltchik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,4,25]]},"reference":[{"key":"8_CR1","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall Inc. (1993)"},{"key":"8_CR2","doi-asserted-by":"publisher","unstructured":"Aissi, H., Mahjoub, A.R., McCormick, S.T., Queyranne, M.: Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs. Math. Program. 154(1-2), 3\u201328 (2015). https:\/\/doi.org\/10.1007\/s10107-015-0944-8","DOI":"10.1007\/s10107-015-0944-8"},{"issue":"3","key":"8_CR3","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1016\/S0166-218X(02)00496-1","volume":"127","author":"YP Aneja","year":"2003","unstructured":"Aneja, Y.P., Chandrasekaran, R., Nair, K.: Parametric min-cuts analysis in a network. Discret. Appl. Math. 127(3), 679\u2013689 (2003). https:\/\/doi.org\/10.1016\/S0166-218X(02)00496-1","journal-title":"Discret. Appl. Math."},{"issue":"2\u20133","key":"8_CR4","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF01692060","volume":"20","author":"M Bauderon","year":"1987","unstructured":"Bauderon, M., Courcelle, B.: Graph expressions and graph rewritings. Math. Syst. Theory 20(2\u20133), 83\u2013127 (1987). https:\/\/doi.org\/10.1007\/BF01692060","journal-title":"Math. Syst. Theory"},{"key":"8_CR5","doi-asserted-by":"publisher","unstructured":"Ben-Nun, T., de Fine Licht, J., Ziogas, A.N., Schneider, T., Hoefler, T.: Stateful dataflow multigraphs: a data-centric model for performance portability on heterogeneous architectures. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2019. Association for Computing Machinery, New York (2019). https:\/\/doi.org\/10.1145\/3295500.3356173","DOI":"10.1145\/3295500.3356173"},{"key":"8_CR6","doi-asserted-by":"publisher","unstructured":"Besta, M., Hoefler, T.: Slim fly: a cost effective low-diameter network topology. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2014, pp. 348\u2013359 (2014). https:\/\/doi.org\/10.1109\/SC.2014.34","DOI":"10.1109\/SC.2014.34"},{"key":"8_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1007\/3-540-48481-7_44","volume-title":"Algorithms - ESA\u2019 99","author":"J Cheriyan","year":"1999","unstructured":"Cheriyan, J., Jord\u00e1n, T., Ravi, R.: On 2-coverings and 2-packings of laminar families. In: Ne\u0161et\u0159il, J. (ed.) ESA 1999. LNCS, vol. 1643, pp. 510\u2013520. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-48481-7_44"},{"issue":"11","key":"8_CR8","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1109\/MC.1980.1653419","volume":"13","author":"WW Chu","year":"1980","unstructured":"Chu, W.W., Holloway, L.J., Lan, M., Efe, K.: Task allocation in distributed data processing. Computer 13(11), 57\u201369 (1980). https:\/\/doi.org\/10.1109\/MC.1980.1653419","journal-title":"Computer"},{"key":"8_CR9","unstructured":"Chv\u00e1tal, V.: Linear Programming. Series of Books in the Mathematical Sciences. W. H. Freeman (1983)"},{"key":"8_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/BFb0035848","volume-title":"STACS 88","author":"B Courcelle","year":"1988","unstructured":"Courcelle, B.: An axiomatic definition of context-free rewriting and its application to NLC graph grammars. In: Cori, R., Wirsing, M. (eds.) STACS 1988. LNCS, vol. 294, pp. 237\u2013247. Springer, Heidelberg (1988). https:\/\/doi.org\/10.1007\/BFb0035848"},{"key":"8_CR11","unstructured":"Dantzig, G.B., Fulkerson, D.R.: On the Max Flow Min Cut Theorem of Networks. RAND Corporation, Santa Monica (1955)"},{"key":"8_CR12","doi-asserted-by":"publisher","unstructured":"Dinh, G., Demmel, J.: Communication-optimal tilings for projective nested loops with arbitrary bounds. In: Scheideler, C., Spear, M. (eds.) 32nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2020, Virtual Event, USA, 15\u201317 July 2020, pp. 523\u2013525. ACM (2020). https:\/\/doi.org\/10.1145\/3350755.3400275","DOI":"10.1145\/3350755.3400275"},{"issue":"2","key":"8_CR13","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1006\/jcss.2001.1790","volume":"64","author":"F Drewes","year":"2002","unstructured":"Drewes, F., Hoffmann, B., Plump, D.: Hierarchical graph transformation. J. Comput. Syst. Sci. 64(2), 249\u2013283 (2002). https:\/\/doi.org\/10.1006\/jcss.2001.1790","journal-title":"J. Comput. Syst. Sci."},{"key":"8_CR14","doi-asserted-by":"publisher","unstructured":"Ehrig, H., Pfender, M., Schneider, H.J.: Graph-grammars: an algebraic approach. In: 14th Annual Symposium on Switching and Automata Theory, Iowa City, Iowa, USA, 15\u201317 October 1973, pp. 167\u2013180 (1973). https:\/\/doi.org\/10.1109\/SWAT.1973.11","DOI":"10.1109\/SWAT.1973.11"},{"key":"8_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/3-540-51498-8_15","volume-title":"Fundamentals of Computation Theory","author":"J Engelfriet","year":"1989","unstructured":"Engelfriet, J.: Context-free NCE graph grammars. In: Csirik, J., Demetrovics, J., G\u00e9cseg, F. (eds.) FCT 1989. LNCS, vol. 380, pp. 148\u2013161. Springer, Heidelberg (1989). https:\/\/doi.org\/10.1007\/3-540-51498-8_15"},{"key":"8_CR16","doi-asserted-by":"publisher","unstructured":"Erickson, J.: Maximum flows and parametric shortest paths in planar graphs. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, 17\u201319 January 2010, pp. 794\u2013804 (2010). https:\/\/doi.org\/10.1137\/1.9781611973075.65","DOI":"10.1137\/1.9781611973075.65"},{"key":"8_CR17","doi-asserted-by":"publisher","unstructured":"Feautrier, P.: Some efficient solutions to the affine scheduling problem. I. One-dimensional time. Int. J. Parallel Program. 21(5), 313\u2013347 (1992). https:\/\/doi.org\/10.1007\/BF01407835","DOI":"10.1007\/BF01407835"},{"issue":"1","key":"8_CR18","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1137\/0218003","volume":"18","author":"G Gallo","year":"1989","unstructured":"Gallo, G., Grigoriadis, M.D., Tarjan, R.E.: A fast parametric maximum flow algorithm and applications. SIAM J. Comput. 18(1), 30\u201355 (1989). https:\/\/doi.org\/10.1137\/0218003","journal-title":"SIAM J. Comput."},{"issue":"8","key":"8_CR19","doi-asserted-by":"publisher","first-page":"1518","DOI":"10.1021\/acs.jcim.6b00159","volume":"56","author":"A Ginsburg","year":"2016","unstructured":"Ginsburg, A., Ben-Nun, T., Asor, R., Shemesh, A., Ringel, I., Raviv, U.: Reciprocal grids: a hierarchical algorithm for computing solution X-ray scattering curves from supramolecular complexes at high resolution. J. Chem. Inf. Model. 56(8), 1518\u20131527 (2016)","journal-title":"J. Chem. Inf. Model."},{"issue":"1\u20132","key":"8_CR20","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s10107-011-0463-1","volume":"135","author":"F Granot","year":"2012","unstructured":"Granot, F., McCormick, S.T., Queyranne, M., Tardella, F.: Structural and algorithmic properties for parametric minimum cuts. Math. Program. 135(1\u20132), 337\u2013367 (2012). https:\/\/doi.org\/10.1007\/s10107-011-0463-1","journal-title":"Math. Program."},{"key":"8_CR21","doi-asserted-by":"publisher","unstructured":"Karger, D.R.: Enumerating parametric global minimum cuts by random interleaving. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, 18\u201321 June 2016, pp. 542\u2013555 (2016). https:\/\/doi.org\/10.1145\/2897518.2897578","DOI":"10.1145\/2897518.2897578"},{"issue":"1","key":"8_CR22","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0166-218X(81)90026-3","volume":"3","author":"RM Karp","year":"1981","unstructured":"Karp, R.M., Orlin, J.B.: Parametric shortest path algorithms with an application to cyclic staffing. Discret. Appl. Math. 3(1), 37\u201345 (1981). https:\/\/doi.org\/10.1016\/0166-218X(81)90026-3","journal-title":"Discret. Appl. Math."},{"key":"8_CR23","doi-asserted-by":"publisher","unstructured":"Kim, J., Dally, W.J., Scott, S., Abts, D.: Technology-driven, highly-scalable dragonfly topology. In: 2008 International Symposium on Computer Architecture, pp. 77\u201388 (2008). https:\/\/doi.org\/10.1109\/ISCA.2008.19","DOI":"10.1109\/ISCA.2008.19"},{"key":"8_CR24","doi-asserted-by":"publisher","unstructured":"Kwasniewski, G., et al.: Pebbles, graphs, and a pinch of combinatorics: towards tight I\/O lower bounds for statically analyzable programs. In: Agrawal, K., Azar, Y. (eds.) 33rd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, 6\u20138 July 2021, SPAA 2021, pp. 328\u2013339. ACM (2021). https:\/\/doi.org\/10.1145\/3409964.3461796","DOI":"10.1145\/3409964.3461796"},{"key":"8_CR25","doi-asserted-by":"publisher","unstructured":"Lattner, C., Adve, V.: LLVM: a compilation framework for lifelong program analysis transformation. In: International Symposium on Code Generation and Optimization, CGO 2004, pp. 75\u201386 (2004). https:\/\/doi.org\/10.1109\/CGO.2004.1281665","DOI":"10.1109\/CGO.2004.1281665"},{"key":"8_CR26","doi-asserted-by":"publisher","unstructured":"Orlin, J.B.: Max flows in O(nm) time, or better. In: Symposium on Theory of Computing Conference, STOC 2013, Palo Alto, CA, USA, 1\u20134 June 2013, pp. 765\u2013774 (2013). https:\/\/doi.org\/10.1145\/2488608.2488705","DOI":"10.1145\/2488608.2488705"},{"issue":"1","key":"8_CR27","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/321679.321682","volume":"19","author":"T Pavlidis","year":"1972","unstructured":"Pavlidis, T.: Linear and context-free graph grammars. J. ACM 19(1), 11\u201322 (1972). https:\/\/doi.org\/10.1145\/321679.321682","journal-title":"J. ACM"},{"issue":"1","key":"8_CR28","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1145\/174608.174610","volume":"12","author":"A Poulovassilis","year":"1994","unstructured":"Poulovassilis, A., Levene, M.: A nested-graph model for the representation and manipulation of complex objects. ACM Trans. Inf. Syst. 12(1), 35\u201368 (1994). https:\/\/doi.org\/10.1145\/174608.174610","journal-title":"ACM Trans. Inf. Syst."},{"issue":"3","key":"8_CR29","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1109\/TC.1985.1676563","volume":"34","author":"C Shen","year":"1985","unstructured":"Shen, C., Tsai, W.: A graph matching approach to optimal task assignment in distributed computing systems using a minimax criterion. IEEE Trans. Comput. 34(3), 197\u2013203 (1985). https:\/\/doi.org\/10.1109\/TC.1985.1676563","journal-title":"IEEE Trans. Comput."},{"key":"8_CR30","doi-asserted-by":"publisher","unstructured":"Valadarsky, A., Shahaf, G., Dinitz, M., Schapira, M.: Xpander: towards optimal-performance datacenters. In: Proceedings of the 12th International on Conference on Emerging Networking EXperiments and Technologies, CoNEXT 2016, pp. 205\u2013219. Association for Computing Machinery, New York (2016). https:\/\/doi.org\/10.1145\/2999572.2999580","DOI":"10.1145\/2999572.2999580"},{"key":"8_CR31","unstructured":"Vasilache, N., et al.: Tensor comprehensions: framework-agnostic high-performance machine learning abstractions. CoRR abs\/1802.04730 (2018)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-30448-4_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T23:03:40Z","timestamp":1684191820000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-30448-4_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031304477","9783031304484"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-30448-4_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"25 April 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Larnaca","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Cyprus","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 June 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 June 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Open","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easy Chair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"49","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"25","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"51% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3 invited papers","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}