{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T06:37:48Z","timestamp":1774334268659,"version":"3.50.1"},"publisher-location":"Singapore","reference-count":27,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819571260","type":"print"},{"value":"9789819571277","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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-981-95-7127-7_7","type":"book-chapter","created":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T10:06:58Z","timestamp":1770977218000},"page":"96-109","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximating the\u00a0Average-Case Graph Search Problem with Non-uniform Costs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-9894-9671","authenticated-orcid":false,"given":"Micha\u0142","family":"Szyfelbein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,14]]},"reference":[{"key":"7_CR1","unstructured":"Angelidakis, H.: Shortest path queries, graph partitioning and covering problems in worst and beyond worst case settings. arXiv abs\/1807.09389 (2018). https:\/\/api.semanticscholar.org\/CorpusID:51718679"},{"issue":"6","key":"7_CR2","doi-asserted-by":"publisher","first-page":"2090","DOI":"10.1137\/S009753979731858X","volume":"28","author":"Y Ben-Asher","year":"1999","unstructured":"Ben-Asher, Y., Farchi, E., Newman, I.: Optimal search in trees. SIAM J. Comput. 28(6), 2090\u20132102 (1999). https:\/\/doi.org\/10.1137\/S009753979731858X","journal-title":"SIAM J. Comput."},{"key":"7_CR3","doi-asserted-by":"publisher","unstructured":"Berendsohn, B., Golinsky, I., Kaplan, H., Kozma, L.: Fast approximation of search trees on trees with centroid trees (2022). https:\/\/doi.org\/10.48550\/arXiv.2209.08024","DOI":"10.48550\/arXiv.2209.08024"},{"key":"7_CR4","doi-asserted-by":"publisher","unstructured":"Berendsohn, B., Kozma, L.: Splay trees on trees, pp. 1875\u20131900 (2022). https:\/\/doi.org\/10.1137\/1.9781611977073.75","DOI":"10.1137\/1.9781611977073.75"},{"issue":"1","key":"7_CR5","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1137\/S0895480195282550","volume":"11","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L., et al.: Rankings of graphs. SIAM J. Discret. Math. 11(1), 168\u2013181 (1998). https:\/\/doi.org\/10.1137\/S0895480195282550","journal-title":"SIAM J. Discret. Math."},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"Charikar, M., Chatziafratis, V.: Approximate hierarchical clustering via sparsest cut and spreading metrics. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pp. 841\u2013854. Society for Industrial and Applied Mathematics, USA (2017)","DOI":"10.1137\/1.9781611974782.53"},{"issue":"4","key":"7_CR7","doi-asserted-by":"publisher","first-page":"1045","DOI":"10.1007\/s00453-012-9715-6","volume":"68","author":"F Cicalese","year":"2012","unstructured":"Cicalese, F., Jacobs, T., Laber, E., Molinaro, M.: Improved approximation algorithms for the average-case tree searching problem. Algorithmica 68(4), 1045\u20131074 (2012). https:\/\/doi.org\/10.1007\/s00453-012-9715-6","journal-title":"Algorithmica"},{"key":"7_CR8","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.tcs.2016.07.019","volume":"647","author":"F Cicalese","year":"2016","unstructured":"Cicalese, F., Keszegh, B., Lidick\u00fd, B., P\u00e1lv\u00f6lgyi, D., Valla, T.: On the tree search problem with non-uniform costs. Theoret. Comput. Sci. 647, 22\u201332 (2016). https:\/\/doi.org\/10.1016\/j.tcs.2016.07.019","journal-title":"Theoret. Comput. Sci."},{"key":"7_CR9","doi-asserted-by":"publisher","unstructured":"Cohen-addad, V., Kanade, V., Mallmann-trenn, F., Mathieu, C.: Hierarchical clustering: objective functions and algorithms. J. ACM 66(4) (2019). https:\/\/doi.org\/10.1145\/3321386","DOI":"10.1145\/3321386"},{"key":"7_CR10","doi-asserted-by":"publisher","unstructured":"Dasgupta, S.: A cost function for similarity-based hierarchical clustering. In: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC 2016, pp. 118\u2013127. Association for Computing Machinery, New York (2016). https:\/\/doi.org\/10.1145\/2897518.2897527","DOI":"10.1145\/2897518.2897527"},{"issue":"8","key":"7_CR11","doi-asserted-by":"publisher","first-page":"1198","DOI":"10.1016\/j.dam.2005.11.005","volume":"154","author":"D Dereniowski","year":"2006","unstructured":"Dereniowski, D.: Edge ranking of weighted trees. Discret. Appl. Math. 154(8), 1198\u20131209 (2006). https:\/\/doi.org\/10.1016\/j.dam.2005.11.005","journal-title":"Discret. Appl. Math."},{"key":"7_CR12","doi-asserted-by":"publisher","unstructured":"Dereniowski, D., Kosowski, A., Uznanski, P., Zou, M.: Approximation strategies for generalized binary search in weighted trees. In: Chatzigiannakis, I., Indyk, P., Kuhn, F., Muscholl, A. (eds.) 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a080, pp. 84:1\u201384:14. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.84","DOI":"10.4230\/LIPIcs.ICALP.2017.84"},{"key":"7_CR13","doi-asserted-by":"publisher","first-page":"985","DOI":"10.1007\/978-3-540-24669-5_127","volume-title":"Parallel Processing and Applied Mathematics","author":"D Dereniowski","year":"2004","unstructured":"Dereniowski, D., Kubale, M.: Cholesky factorization of matrices in parallel and ranking of graphs. In: Wyrzykowski, R., Dongarra, J., Paprzycki, M., Wa\u015bniewski, J. (eds.) Parallel Processing and Applied Mathematics, pp. 985\u2013992. Springer, Heidelberg (2004)"},{"key":"7_CR14","doi-asserted-by":"publisher","unstructured":"Dereniowski, D., Kubale, M.: Efficient parallel query processing by graph ranking. Fundam. Inform. 69, 273\u2013285 (2006). https:\/\/doi.org\/10.3233\/FUN-2006-69302","DOI":"10.3233\/FUN-2006-69302"},{"key":"7_CR15","doi-asserted-by":"publisher","unstructured":"Dereniowski, D., Wrosz, I.: Constant-factor approximation algorithm for binary search in trees with monotonic query times. In: Szeider, S., Ganian, R., Silva, A. (eds.) 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0241, pp. 42:1\u201342:15. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2022). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2022.42","DOI":"10.4230\/LIPIcs.MFCS.2022.42"},{"key":"7_CR16","unstructured":"Dereniowski, D., Wrosz, I.: Searching in trees with monotonic query times (2024). https:\/\/arxiv.org\/abs\/2401.13747"},{"key":"7_CR17","doi-asserted-by":"publisher","unstructured":"Feige, U., Hajiaghayi, M., Lee, J.R.: Improved approximation algorithms for minimum-weight vertex separators. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC 2005, pp. 563\u2013572. Association for Computing Machinery, New York (2005). https:\/\/doi.org\/10.1145\/1060590.1060674","DOI":"10.1145\/1060590.1060674"},{"key":"7_CR18","unstructured":"Iyer, A.V., Ratliff, H.D., Vijayan, G.: Parallel assembly of modular products\u2014an analysis. Technical Report 88-06, Georgia Institute of Technology, Atlanta, Georgia (1988)"},{"key":"7_CR19","unstructured":"Knuth, D.: The Art of Computer Programming, vol. 3: Sorting and Searching. Addison-Wesley (1973)"},{"key":"7_CR20","doi-asserted-by":"publisher","unstructured":"Makino, K., Uno, Y., Ibaraki, T.: On minimum edge ranking spanning trees. J. Algorithms 38(2), 411\u2013437 (2001). https:\/\/doi.org\/10.1006\/jagm.2000.1143. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S019667740091143X","DOI":"10.1006\/jagm.2000.1143"},{"key":"7_CR21","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1007\/3-540-36136-7_38","volume-title":"Algorithms and Computation","author":"K Makino","year":"2002","unstructured":"Makino, K., Uno, Y., Ibaraki, T.: Minimum edge ranking spanning trees of threshold graphs. In: Bose, P., Morin, P. (eds.) Algorithms and Computation, pp. 428\u2013440. Springer, Heidelberg (2002)"},{"key":"7_CR22","unstructured":"Mozes, S., Onak, K., Weimann, O.: Finding an optimal tree searching strategy in linear time. In: Teng, S. (ed.) Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, 20\u201322 January 2008, pp. 1096\u20131105. SIAM (2008). http:\/\/dl.acm.org\/citation.cfm?id=1347082.1347202"},{"key":"7_CR23","doi-asserted-by":"publisher","unstructured":"Onak, K., Parys, P.: Generalization of binary search: searching in trees and forest-like partial orders. In: 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 379\u2013388 (2006). https:\/\/doi.org\/10.1109\/FOCS.2006.32","DOI":"10.1109\/FOCS.2006.32"},{"key":"7_CR24","unstructured":"Pothen, A.: The complexity of optimal elimination trees. Technical Report CS-88-16, Pennsylvania State University, Department of Computer Science, Penn State University CS-88-16 (1988)"},{"issue":"2","key":"7_CR25","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0020-0190(89)90161-0","volume":"33","author":"AA Sch\u00e4ffer","year":"1989","unstructured":"Sch\u00e4ffer, A.A.: Optimal node ranking of trees in linear time. Inf. Process. Lett. 33(2), 91\u201396 (1989). https:\/\/doi.org\/10.1016\/0020-0190(89)90161-0","journal-title":"Inf. Process. Lett."},{"key":"7_CR26","doi-asserted-by":"publisher","unstructured":"Sen, A., Deng, H., Guha, S.: On a graph partition problem with application to VLSI layout. Inf. Process. Lett. 43(2), 87\u201394 (1992). https:\/\/doi.org\/10.1016\/0020-0190(92)90017-P. https:\/\/www.sciencedirect.com\/science\/article\/pii\/002001909290017P","DOI":"10.1016\/0020-0190(92)90017-P"},{"key":"7_CR27","unstructured":"Szyfelbein, M.: Searching in trees with k-up-modular cost functions (2025). https:\/\/arxiv.org\/abs\/2504.17887"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-95-7127-7_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T04:15:21Z","timestamp":1774325721000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-95-7127-7_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9789819571260","9789819571277"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-981-95-7127-7_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"14 February 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that\u00a0are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"WALCOM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference and Workshops on Algorithms and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Perugia","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 March 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 March 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"walcom2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/mozart.diei.unipg.it\/walcom2026","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}