{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T20:17:50Z","timestamp":1757621870216,"version":"3.44.0"},"publisher-location":"Cham","reference-count":13,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783032002808"},{"type":"electronic","value":"9783032002815"}],"license":[{"start":{"date-parts":[[2025,8,11]],"date-time":"2025-08-11T00:00:00Z","timestamp":1754870400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,11]],"date-time":"2025-08-11T00:00:00Z","timestamp":1754870400000},"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-00281-5_9","type":"book-chapter","created":{"date-parts":[[2025,8,10]],"date-time":"2025-08-10T11:38:30Z","timestamp":1754825910000},"page":"121-148","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Subquadratic Time Algorithm for\u00a0the\u00a0Weighted k-Center Problem on\u00a0Cactus Graphs"],"prefix":"10.1007","author":[{"given":"Binay","family":"Bhattacharya","sequence":"first","affiliation":[]},{"given":"Sandip","family":"Das","sequence":"additional","affiliation":[]},{"given":"Subhadeep Ranjan","family":"Dev","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,11]]},"reference":[{"key":"9_CR1","unstructured":"Aritra Banik, Binay Bhattacharya, Sandip Das, Tsunehiko Kameda, and Zhao Song. The $$p$$-center problem in tree networks revisited. In 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016"},{"issue":"3","key":"9_CR2","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/j.tcs.2007.02.033","volume":"378","author":"B Ben-Moshe","year":"2007","unstructured":"Ben-Moshe, B., Bhattacharya, B., Shi, Q., Tamir, A.: Efficient algorithms for center problems in cactus networks. Theoret. Comput. Sci. 378(3), 237\u2013252 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"9_CR3","unstructured":"Binay Bhattacharya, Sandip Das, and Subhadeep\u00a0Ranjan Dev. The weighted $$k$$-center problem in trees for fixed $$k$$. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Binay Bhattacharya, Mordecai\u00a0J Golin, Yuya Higashikawa, Tsunehiko Kameda, and Naoki Katoh. Improved algorithms for computing $$k$$-sink on dynamic flow path networks. In Workshop on Algorithms and Data Structures, pages 133\u2013144. Springer, 2017","DOI":"10.1007\/978-3-319-62127-2_12"},{"issue":"2","key":"9_CR5","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/j.comgeo.2009.07.003","volume":"47","author":"B Bhattacharya","year":"2014","unstructured":"Bhattacharya, B., Shi, Q.: Improved algorithms to network $$p$$-center location problems. Comput. Geom. 47(2), 307\u2013315 (2014)","journal-title":"Comput. Geom."},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"Danny\u00a0Z Chen and Haitao Wang. A note on searching line arrangements and applications. Information Processing Letters, 113(14-16):518\u2013521, 2013","DOI":"10.1016\/j.ipl.2013.04.011"},{"key":"9_CR7","unstructured":"Greg\u00a0N Frederickson. Optimal algorithms for tree partitioning. In Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, pages 168\u2013177, 1991"},{"key":"9_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/BFb0028271","volume-title":"Algorithms and Data Structures","author":"GN Frederickson","year":"1991","unstructured":"Frederickson, G.N.: Parametric search and locating supply centers in trees. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1991. LNCS, vol. 519, pp. 299\u2013319. Springer, Heidelberg (1991). https:\/\/doi.org\/10.1007\/BFb0028271"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"Greg\u00a0N Frederickson and Donald\u00a0B Johnson. Finding $$k$$th paths and $$p$$-centers by generating and searching good data structures. Journal of Algorithms, 4(1):61\u201380, 1983","DOI":"10.1016\/0196-6774(83)90035-4"},{"key":"9_CR10","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/j.tcs.2014.09.046","volume":"562","author":"A Gavruskin","year":"2015","unstructured":"Gavruskin, A., Khoussainov, B., Kokho, M., Liu, J.: Dynamic algorithms for monotonic interval scheduling problem. Theoret. Comput. Sci. 562, 227\u2013242 (2015)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"9_CR11","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0020-0190(91)90165-E","volume":"40","author":"W-L Hsu","year":"1991","unstructured":"Hsu, W.-L., Tsai, K.-H.: Linear time algorithms on circular-arc graphs. Inf. Process. Lett. 40(3), 123\u2013129 (1991)","journal-title":"Inf. Process. Lett."},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Oded Kariv and S\u00a0Louis Hakimi. An algorithmic approach to network location problems. I: The $$p$$-centers. SIAM Journal on Applied Mathematics, 37(3):513\u2013538, 1979","DOI":"10.1137\/0137040"},{"key":"9_CR13","unstructured":"Haitao Wang and Jingru Zhang. An $$O(n \\log n)$$-time algorithm for the $$k$$-center problem in trees. In 34th International Symposium on Computational Geometry (SoCG 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018"}],"container-title":["Lecture Notes in Computer Science","Discrete and Computational Geometry, Graphs, and Games"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-00281-5_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T16:01:01Z","timestamp":1757347261000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-00281-5_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,11]]},"ISBN":["9783032002808","9783032002815"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-00281-5_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025,8,11]]},"assertion":[{"value":"11 August 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"JCDCGGG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Japanese Conference on Discrete and Computational Geometry, Graphs, and Games","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 September 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 September 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"jcdcg2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.alg.cei.uec.ac.jp\/itohiro\/JCDCGG\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}