{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T08:16:26Z","timestamp":1743063386546,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030835071"},{"type":"electronic","value":"9783030835088"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-83508-8_25","type":"book-chapter","created":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T13:05:06Z","timestamp":1627650306000},"page":"343-356","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Stronger Lower Bound on Parametric Minimum Spanning Trees"],"prefix":"10.1007","author":[{"given":"David","family":"Eppstein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,31]]},"reference":[{"key":"25_CR1","doi-asserted-by":"publisher","unstructured":"Agarwal, P.K., Eppstein, D., Guibas, L.J., Henzinger, M.R.: Parametric and kinetic minimum spanning trees. In: Proceedings of the 39th IEEE Symposium on Foundations of Computer Science (FOCS 1998), pp. 596\u2013605 (1998). https:\/\/doi.org\/10.1109\/SFCS.1998.743510","DOI":"10.1109\/SFCS.1998.743510"},{"key":"25_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1007\/11785293_37","volume-title":"Algorithm Theory \u2013 SWAT 2006","author":"J Carlson","year":"2006","unstructured":"Carlson, J., Eppstein, D.: The weighted maximum-mean subtree and other bicriterion subtree problems. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol. 4059, pp. 400\u2013410. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11785293_37"},{"key":"25_CR3","unstructured":"Carstensen, P.J.: Parametric cost shortest path problems. Unpublished Bellcore memo (1984)"},{"issue":"1","key":"25_CR4","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/net.21701","volume":"69","author":"L Castelli","year":"2017","unstructured":"Castelli, L., Labb\u00e9, M., Violin, A.: Network pricing problem with unit toll. Networks 69(1), 83\u201393 (2017). https:\/\/doi.org\/10.1002\/net.21701","journal-title":"Networks"},{"key":"25_CR5","doi-asserted-by":"publisher","unstructured":"Chakraborty, S., Fischer, E., Lachish, O., Yuster, R.: Two-phase algorithms for the parametric shortest path problem. In: Marion, J.-Y., Schwentick, T. (eds.) Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010), Volume 5 of LIPIcs, pp. 167\u2013178. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2010). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2010.2452","DOI":"10.4230\/LIPIcs.STACS.2010.2452"},{"key":"25_CR6","unstructured":"Chan, T.M.: Finding the shortest bottleneck edge in a parametric minimum spanning tree. In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 917\u2013918. SIAM (2005). https:\/\/dl.acm.org\/citation.cfm?id=1070432.1070561"},{"issue":"3","key":"25_CR7","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/PL00009354","volume":"19","author":"TK Dey","year":"1998","unstructured":"Dey, T.K.: Improved bounds for planar $$k$$-sets and related problems. Discrete Comput. Geom. 19(3), 373\u2013382 (1998). https:\/\/doi.org\/10.1007\/PL00009354","journal-title":"Discrete Comput. Geom."},{"issue":"11","key":"25_CR8","doi-asserted-by":"publisher","first-page":"1565","DOI":"10.1287\/mnsc.42.11.1565","volume":"42","author":"M Eben-Chaime","year":"1996","unstructured":"Eben-Chaime, M.: Parametric solution for linear bicriteria knapsack models. Manag. Sci. 42(11), 1565\u20131575 (1996). https:\/\/doi.org\/10.1287\/mnsc.42.11.1565","journal-title":"Manag. Sci."},{"issue":"4","key":"25_CR9","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/PL00009396","volume":"20","author":"D Eppstein","year":"1998","unstructured":"Eppstein, D.: Geometric lower bounds for parametric matroid optimization. Discrete Comput. Geom. 20(4), 463\u2013476 (1998). https:\/\/doi.org\/10.1007\/PL00009396","journal-title":"Discrete Comput. Geom."},{"key":"25_CR10","doi-asserted-by":"publisher","unstructured":"Eppstein, D.: The parametric closure problem. ACM Trans. Algorithms 14(1), A2:1\u2013A2:22 (2018). https:\/\/doi.org\/10.1145\/3147212","DOI":"10.1145\/3147212"},{"key":"25_CR11","doi-asserted-by":"publisher","unstructured":"Erickson, J.: Maximum flows and parametric shortest paths in planar graphs. In: Charikar, M. (ed.) Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pp. 794\u2013804. SIAM (2010). https:\/\/doi.org\/10.1137\/1.9781611973075.65","DOI":"10.1137\/1.9781611973075.65"},{"issue":"1","key":"25_CR12","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/S0304-3975(96)00262-9","volume":"181","author":"D Fern\u00e1ndez-Baca","year":"1997","unstructured":"Fern\u00e1ndez-Baca, D., Slutzki, G.: Linear-time algorithms for parametric minimum spanning tree problems on planar graphs. Theor. Comput. Sci. 181(1), 57\u201374 (1997). https:\/\/doi.org\/10.1016\/S0304-3975(96)00262-9","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"25_CR13","first-page":"352","volume":"3","author":"D Fern\u00e1ndez-Baca","year":"1996","unstructured":"Fern\u00e1ndez-Baca, D., Slutzki, G., Eppstein, D.: Using sparsification for parametric minimum spanning tree problems. Nordic J. Comput. 3(4), 352\u2013366 (1996)","journal-title":"Nordic J. Comput."},{"issue":"3","key":"25_CR14","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1016\/0196-6774(88)90031-4","volume":"9","author":"HN Gabow","year":"1988","unstructured":"Gabow, H.N., Tarjan, R.E.: Algorithms for two bottleneck optimization problems. J. Algorithms 9(3), 411\u2013417 (1988). https:\/\/doi.org\/10.1016\/0196-6774(88)90031-4","journal-title":"J. Algorithms"},{"key":"25_CR15","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.ipl.2016.12.003","volume":"120","author":"A Giudici","year":"2017","unstructured":"Giudici, A., Halffmann, P., Ruzika, S., Thielen, C.: Approximation schemes for the parametric knapsack problem. Inf. Process. Lett. 120, 11\u201315 (2017). https:\/\/doi.org\/10.1016\/j.ipl.2016.12.003","journal-title":"Inf. Process. Lett."},{"key":"25_CR16","unstructured":"Gusfield, D.: Bounds for the parametric minimum spanning tree problem. In: Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State University, Arcata, California, 1979), Volume 26 of Congress Number, Winnipeg, Manitoba, pp. 173\u2013181. Utilitas Math (1980)"},{"key":"25_CR17","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.ipl.2017.06.006","volume":"126","author":"M Holzhauser","year":"2017","unstructured":"Holzhauser, M., Krumke, S.O.: An FPTAS for the parametric knapsack problem. Inf. Process. Lett. 126, 43\u201347 (2017). https:\/\/doi.org\/10.1016\/j.ipl.2017.06.006","journal-title":"Inf. Process. Lett."},{"key":"25_CR18","unstructured":"Katoh, N.: Bicriteria network optimization problems. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E75, A:321\u2013A:329 (1992)"},{"key":"25_CR19","doi-asserted-by":"publisher","unstructured":"Katoh, N., Tokuyama, T.: Notes on computing peaks in $$k$$-levels and parametric spanning trees. In: Souvaine, D.L. (ed.) Proceedings of the 17th Symposium on Computational Geometry (SoCG 2001), pp. 241\u2013248. ACM (2001). https:\/\/doi.org\/10.1145\/378583.378675","DOI":"10.1145\/378583.378675"},{"issue":"5","key":"25_CR20","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0020-0190(79)90075-9","volume":"9","author":"SL Mitchell","year":"1979","unstructured":"Mitchell, S.L.: Linear algorithms to recognize outerplanar and maximal outerplanar graphs. Inf. Process. Lett. 9(5), 229\u2013232 (1979). https:\/\/doi.org\/10.1016\/0020-0190(79)90075-9","journal-title":"Inf. Process. Lett."},{"key":"25_CR21","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1287\/opre.8.5.733","volume":"8","author":"M Pollack","year":"1960","unstructured":"Pollack, M.: The maximum capacity route through a network. Oper. Res. 8, 733\u2013736 (1960). https:\/\/doi.org\/10.1287\/opre.8.5.733","journal-title":"Oper. Res."},{"key":"25_CR22","doi-asserted-by":"publisher","unstructured":"Tarjan, R.E.: Data Structures and Network Algorithms, Volume 44 of CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics (1983). https:\/\/doi.org\/10.1137\/1.9781611970265","DOI":"10.1137\/1.9781611970265"},{"issue":"2","key":"25_CR23","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1002\/net.3230130202","volume":"13","author":"JA Wald","year":"1983","unstructured":"Wald, J.A., Colbourn, C.J.: Steiner trees, partial 2-trees, and minimum IFI networks. Networks 13(2), 159\u2013167 (1983). https:\/\/doi.org\/10.1002\/net.3230130202","journal-title":"Networks"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-83508-8_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,18]],"date-time":"2022-02-18T11:27:36Z","timestamp":1645183656000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-83508-8_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030835071","9783030835088"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-83508-8_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"31 July 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Workshop on Algorithms and Data Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 August 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 August 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/projects.cs.dal.ca\/wads2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"123","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":"47","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":"38% - 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.1","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":"13","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)"}}]}}