{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T16:58:20Z","timestamp":1743008300998,"version":"3.40.3"},"publisher-location":"Cham","reference-count":42,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030799861"},{"type":"electronic","value":"9783030799878"}],"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-79987-8_19","type":"book-chapter","created":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T23:05:05Z","timestamp":1625007905000},"page":"265-281","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["An Efficient Noisy Binary Search in Graphs via Median Approximation"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4000-4818","authenticated-orcid":false,"given":"Dariusz","family":"Dereniowski","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1808-8330","authenticated-orcid":false,"given":"Aleksander","family":"\u0141ukasiewicz","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8652-0490","authenticated-orcid":false,"given":"Przemys\u0142aw","family":"Uzna\u0144ski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,30]]},"reference":[{"key":"19_CR1","doi-asserted-by":"publisher","unstructured":"Abboud, A., Grandoni, F., Williams, V.V.: Subcubic equivalences between graph centrality problems, APSP and diameter. In: SODA 2015, pp. 1681\u20131697 (2015). https:\/\/doi.org\/10.1137\/1.9781611973730.112","DOI":"10.1137\/1.9781611973730.112"},{"key":"19_CR2","doi-asserted-by":"publisher","unstructured":"Abboud, A., Williams, V.V., Wang, J.R.: Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In: SODA 2016, pp. 377\u2013391 (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch28","DOI":"10.1137\/1.9781611974331.ch28"},{"issue":"5","key":"19_CR3","doi-asserted-by":"publisher","first-page":"41:1","DOI":"10.1145\/2985473","volume":"63","author":"I Abraham","year":"2016","unstructured":"Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway dimension and provably efficient shortest path algorithms. J. ACM 63(5), 41:1\u201341:26 (2016). https:\/\/doi.org\/10.1145\/2985473","journal-title":"J. ACM"},{"issue":"1","key":"19_CR4","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1006\/jcta.1996.0036","volume":"74","author":"M Aigner","year":"1996","unstructured":"Aigner, M.: Searching with lies. J. Comb. Theory Ser. A 74(1), 43\u201356 (1996). https:\/\/doi.org\/10.1006\/jcta.1996.0036","journal-title":"J. Comb. Theory Ser. A"},{"issue":"6","key":"19_CR5","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1121\/1.1906679","volume":"22","author":"A Bavelas","year":"1950","unstructured":"Bavelas, A.: Communication patterns in task-oriented groups. J. Acoust. Soc. Am. 22(6), 725\u2013730 (1950). https:\/\/doi.org\/10.1121\/1.1906679","journal-title":"J. Acoust. Soc. Am."},{"issue":"2","key":"19_CR6","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1002\/bs.3830100205","volume":"10","author":"MA Beauchamp","year":"1965","unstructured":"Beauchamp, M.A.: An improved index of centrality. Behav. Sci. 10(2), 161\u2013163 (1965). https:\/\/doi.org\/10.1002\/bs.3830100205","journal-title":"Behav. Sci."},{"issue":"6","key":"19_CR7","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":"19_CR8","doi-asserted-by":"publisher","unstructured":"Ben-Or, M., Hassidim, A.: The Bayesian learner is optimal for noisy binary search (and pretty good for quantum as well). In: FOCS 2008, pp. 221\u2013230 (2008). https:\/\/doi.org\/10.1109\/FOCS.2008.58","DOI":"10.1109\/FOCS.2008.58"},{"key":"19_CR9","unstructured":"B\u00e9n\u00e9teau, L., Chalopin, J., Chepoi, V., Vax\u00e8s, Y.: Medians in median graphs in linear time. CoRR abs\/1907.10398 (2019)"},{"key":"19_CR10","doi-asserted-by":"publisher","unstructured":"Boczkowski, L., Korman, A., Rodeh, Y.: Searching a tree with permanently noisy advice. In: ESA 2018, pp. 54:1\u201354:13 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2018.54","DOI":"10.4230\/LIPIcs.ESA.2018.54"},{"key":"19_CR11","doi-asserted-by":"publisher","unstructured":"Borgstrom, R.S., Kosaraju, S.R.: Comparison-based search in the presence of errors. In: STOC 1993, pp. 130\u2013136 (1993). https:\/\/doi.org\/10.1145\/167088.167129","DOI":"10.1145\/167088.167129"},{"key":"19_CR12","doi-asserted-by":"publisher","unstructured":"Cabello, S.: Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. In: SODA 2017, pp. 2143\u20132152 (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.139","DOI":"10.1137\/1.9781611974782.139"},{"issue":"2","key":"19_CR13","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1137\/S1052623403424740","volume":"16","author":"D Cantone","year":"2005","unstructured":"Cantone, D., Cincotti, G., Ferro, A., Pulvirenti, A.: An efficient approximate algorithm for the 1-median problem in metric spaces. SIAM J. Optim. 16(2), 434\u2013451 (2005). https:\/\/doi.org\/10.1137\/S1052623403424740","journal-title":"SIAM J. Optim."},{"key":"19_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2011.12.003","volume":"426","author":"C Chang","year":"2012","unstructured":"Chang, C.: Some results on approximate 1-median selection in metric spaces. Theor. Comput. Sci. 426, 1\u201312 (2012). https:\/\/doi.org\/10.1016\/j.tcs.2011.12.003","journal-title":"Theor. Comput. Sci."},{"key":"19_CR15","doi-asserted-by":"publisher","unstructured":"Chechik, S., Cohen, E., Kaplan, H.: Average distance queries through weighted samples in graphs and metric spaces: high scalability with tight statistical guarantees. In: APPROX-RANDOM 2015, pp. 659\u2013679 (2015). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2015.659","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2015.659"},{"key":"19_CR16","doi-asserted-by":"publisher","unstructured":"Dagan, Y., Filmus, Y., Gabizon, A., Moran, S.: Twenty (simple) questions. In: STOC 2017, pp. 9\u201321 (2017). https:\/\/doi.org\/10.1145\/3055399.3055422","DOI":"10.1145\/3055399.3055422"},{"issue":"5","key":"19_CR17","doi-asserted-by":"publisher","first-page":"1757","DOI":"10.1007\/s00453-018-0501-y","volume":"81","author":"A Deligkas","year":"2018","unstructured":"Deligkas, A., Mertzios, G.B., Spirakis, P.G.: Binary search in graphs revisited. Algorithmica 81(5), 1757\u20131780 (2018). https:\/\/doi.org\/10.1007\/s00453-018-0501-y","journal-title":"Algorithmica"},{"issue":"13","key":"19_CR18","doi-asserted-by":"publisher","first-page":"2493","DOI":"10.1016\/j.dam.2008.03.007","volume":"156","author":"D Dereniowski","year":"2008","unstructured":"Dereniowski, D.: Edge ranking and searching in partial orders. Discret. Appl. Math. 156(13), 2493\u20132500 (2008). https:\/\/doi.org\/10.1016\/j.dam.2008.03.007","journal-title":"Discret. Appl. Math."},{"key":"19_CR19","doi-asserted-by":"publisher","unstructured":"Dereniowski, D., Kosowski, A., Uzna\u0144ski, P., Zou, M.: Approximation strategies for generalized binary search in weighted trees. In: ICALP 2017, pp. 84:1\u201384:14 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.84","DOI":"10.4230\/LIPIcs.ICALP.2017.84"},{"key":"19_CR20","doi-asserted-by":"publisher","unstructured":"Dereniowski, D., Tiegel, S., Uzna\u0144ski, P., Wolleb-Graf, D.: A framework for searching in graphs in the presence of errors. In: SOSA@SODA 2019, pp. 4:1\u20134:17 (2019). https:\/\/doi.org\/10.4230\/OASIcs.SOSA.2019.4","DOI":"10.4230\/OASIcs.SOSA.2019.4"},{"key":"19_CR21","unstructured":"Dhagat, A., G\u00e1cs, P., Winkler, P.: On playing \u201ctwenty questions\u201d with a liar. In: SODA 1992, pp. 16\u201322 (1992)"},{"key":"19_CR22","unstructured":"Emamjomeh-Zadeh, E., Kempe, D.: A general framework for robust interactive learning. In: NIPS 2017, pp. 7085\u20137094 (2007)"},{"key":"19_CR23","doi-asserted-by":"publisher","unstructured":"Emamjomeh-Zadeh, E., Kempe, D., Singhal, V.: Deterministic and probabilistic binary search in graphs. In: STOC 2016, pp. 519\u2013532 (2016). https:\/\/doi.org\/10.1145\/2897518.2897656","DOI":"10.1145\/2897518.2897656"},{"issue":"5","key":"19_CR24","doi-asserted-by":"publisher","first-page":"1001","DOI":"10.1137\/S0097539791195877","volume":"23","author":"U Feige","year":"1994","unstructured":"Feige, U., Raghavan, P., Peleg, D., Upfal, E.: Computing with noisy information. SIAM J. Comput. 23(5), 1001\u20131018 (1994). https:\/\/doi.org\/10.1137\/S0097539791195877","journal-title":"SIAM J. Comput."},{"issue":"3","key":"19_CR25","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0378-8733(78)90021-7","volume":"1","author":"LC Freeman","year":"1978","unstructured":"Freeman, L.C.: Centrality in social networks conceptual clarification. Soc. Netw. 1(3), 215\u2013239 (1978)","journal-title":"Soc. Netw."},{"issue":"1","key":"19_CR26","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.jalgor.2004.05.002","volume":"53","author":"C Gavoille","year":"2004","unstructured":"Gavoille, C., Peleg, D., P\u00e9rennes, S., Raz, R.: Distance labeling in graphs. J. Algorithms 53(1), 85\u2013112 (2004). https:\/\/doi.org\/10.1016\/j.jalgor.2004.05.002","journal-title":"J. Algorithms"},{"issue":"3","key":"19_CR27","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1287\/opre.12.3.450","volume":"12","author":"SL Hakimi","year":"1964","unstructured":"Hakimi, S.L.: Optimum locations of switching centers and the absolute centers and medians of a graph. Oper. Res. 12(3), 450\u2013459 (1964)","journal-title":"Oper. Res."},{"key":"19_CR28","doi-asserted-by":"publisher","unstructured":"Indyk, P.: Sublinear time algorithms for metric space problems. In: STOC 1999, pp. 428\u2013434 (1999). https:\/\/doi.org\/10.1145\/301250.301366","DOI":"10.1145\/301250.301366"},{"key":"19_CR29","unstructured":"Karp, R.M., Kleinberg, R.: Noisy binary search and its applications. In: SODA 2007, pp. 881\u2013890 (2007)"},{"key":"19_CR30","doi-asserted-by":"publisher","unstructured":"Kosowski, A., Viennot, L.: Beyond highway dimension: Small distance labels using tree skeletons. In: SODA 2017, pp. 1462\u20131478 (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.95","DOI":"10.1137\/1.9781611974782.95"},{"issue":"1","key":"19_CR31","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1007\/s004530010076","volume":"30","author":"TW Lam","year":"2001","unstructured":"Lam, T.W., Yue, F.L.: Optimal edge ranking of trees in linear time. Algorithmica 30(1), 12\u201333 (2001). https:\/\/doi.org\/10.1007\/s004530010076","journal-title":"Algorithmica"},{"key":"19_CR32","unstructured":"Mozes, S., Onak, K., Weimann, O.: Finding an optimal tree searching strategy in linear time. In: SODA 2008, pp. 1096\u20131105 (2008)"},{"key":"19_CR33","doi-asserted-by":"publisher","unstructured":"Onak, K., Parys, P.: Generalization of binary search: searching in trees and forest-like partial orders. In: FOCS 2006, pp. 379\u2013388 (2006). https:\/\/doi.org\/10.1109\/FOCS.2006.32","DOI":"10.1109\/FOCS.2006.32"},{"issue":"4","key":"19_CR34","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1287\/opre.26.4.597","volume":"26","author":"LM Ostresh","year":"1978","unstructured":"Ostresh, L.M.: On the convergence of a class of iterative methods for solving the weber location problem. Oper. Res. 26(4), 597\u2013609 (1978). https:\/\/doi.org\/10.1287\/opre.26.4.597","journal-title":"Oper. Res."},{"issue":"3","key":"19_CR35","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1016\/0022-0000(80)90014-8","volume":"20","author":"RL Rivest","year":"1980","unstructured":"Rivest, R.L., Meyer, A.R., Kleitman, D.J., Winklmann, K., Spencer, J.: Coping with errors in binary search procedures. J. Comput. Syst. Sci. 20(3), 396\u2013404 (1980). https:\/\/doi.org\/10.1016\/0022-0000(80)90014-8","journal-title":"J. Comput. Syst. Sci."},{"key":"19_CR36","first-page":"505","volume":"6B","author":"A R\u00e9nyi","year":"1961","unstructured":"R\u00e9nyi, A.: On a problem of information theory. MTA Mat. Kut. Int. Kozl. 6B, 505\u2013516 (1961)","journal-title":"MTA Mat. Kut. Int. Kozl."},{"issue":"4","key":"19_CR37","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1007\/bf02289527","volume":"31","author":"G Sabidussi","year":"1966","unstructured":"Sabidussi, G.: The centrality index of a graph. Psychometrika 31(4), 581\u2013603 (1966). https:\/\/doi.org\/10.1007\/bf02289527","journal-title":"Psychometrika"},{"issue":"2","key":"19_CR38","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":"19_CR39","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/978-3-642-33492-4_15","volume-title":"Discovery Science","author":"K Tabata","year":"2012","unstructured":"Tabata, K., Nakamura, A., Kudo, M.: Fast approximation algorithm for the 1-median problem. In: Ganascia, J.-G., Lenca, P., Petit, J.-M. (eds.) DS 2012. LNCS (LNAI), vol. 7569, pp. 169\u2013183. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-33492-4_15"},{"issue":"5","key":"19_CR40","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1587\/transinf.2016EDP7398","volume":"100\u2013D","author":"K Tabata","year":"2017","unstructured":"Tabata, K., Nakamura, A., Kudo, M.: An efficient approximate algorithm for the 1-median problem on a graph. IEICE Trans. Inf. Syst. 100\u2013D(5), 994\u20131002 (2017). https:\/\/doi.org\/10.1587\/transinf.2016EDP7398","journal-title":"IEICE Trans. Inf. Syst."},{"issue":"4","key":"19_CR41","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1287\/mnsc.29.4.482","volume":"29","author":"BC Tansel","year":"1983","unstructured":"Tansel, B.C., Francis, R.L., Lowe, T.J.: State of the art-location on networks: a survey. Part I: the p-center and p-median problems. Manag. Sci. 29(4), 482\u2013497 (1983)","journal-title":"Manag. Sci."},{"key":"19_CR42","doi-asserted-by":"publisher","DOI":"10.1063\/1.3024514","volume-title":"Adventures of a Mathematician","author":"SM Ulam","year":"1976","unstructured":"Ulam, S.M.: Adventures of a Mathematician. Scribner, New York (1976)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-79987-8_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T23:13:07Z","timestamp":1625008387000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-79987-8_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030799861","9783030799878"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-79987-8_19","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":"30 June 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ottawa, ON","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 July 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 July 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"32","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/iwoca2021.eecs.uottawa.ca\/","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":"107","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":"38","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":"36% - 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":"9.1","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":"The workshop was held virtually.","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)"}}]}}