{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T14:05:19Z","timestamp":1784383519329,"version":"3.55.0"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031987397","type":"print"},{"value":"9783031987403","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-98740-3_8","type":"book-chapter","created":{"date-parts":[[2025,7,17]],"date-time":"2025-07-17T23:48:29Z","timestamp":1752796109000},"page":"103-117","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Exact Learning of\u00a0Weighted Graphs Using Composite Queries"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8943-191X","authenticated-orcid":false,"given":"Michael T.","family":"Goodrich","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-1255-7156","authenticated-orcid":false,"given":"Songyu","family":"Liu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ioannis","family":"Panageas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,7,18]]},"reference":[{"key":"8_CR1","doi-asserted-by":"publisher","unstructured":"Abrahao, B., Chierichetti, F., Kleinberg, R., Panconesi, A.: Trace complexity of network inference. In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013, pp. 491\u2013499. ACM, Chicago (2013). https:\/\/doi.org\/10.1145\/2487575.2487664, https:\/\/dl.acm.org\/doi\/10.1145\/2487575.2487664","DOI":"10.1145\/2487575.2487664"},{"key":"8_CR2","doi-asserted-by":"publisher","unstructured":"Afshar, R., Goodrich, M.T.: Exact learning of multitrees and almost-trees using path queries. In: Latin American Symposium on Theoretical Informatics, pp. 293\u2013311 (Aug 2022). https:\/\/doi.org\/10.48550\/arXiv.2208.04216, https:\/\/www.semanticscholar.org\/paper\/a11e550eff669a4056d3957693fceb60add0bd47, arXiv:2208.04216 [cs]","DOI":"10.48550\/arXiv.2208.04216"},{"key":"8_CR3","doi-asserted-by":"publisher","unstructured":"Afshar, R., Goodrich, M.T., Matias, P., Osegueda, M.C.: Reconstructing biological and digital phylogenetic trees in parallel. Drops-idn\/v2\/document\/10.4230\/lipics.esa.2020.3 (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2020.3, https:\/\/drops.dagstuhl.de\/entities\/document\/10.4230\/LIPIcs.ESA.2020.3","DOI":"10.4230\/LIPIcs.ESA.2020.3"},{"key":"8_CR4","doi-asserted-by":"publisher","unstructured":"Afshar, R., Goodrich, M.T., Matias, P., Osegueda, M.C.: Mapping networks via parallel kth-hop traceroute queries. Drops-idn\/v2\/document\/10.4230\/lipics.stacs.2022.4 (2022). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2022.4, https:\/\/drops.dagstuhl.de\/entities\/document\/10.4230\/LIPIcs.STACS.2022.4","DOI":"10.4230\/LIPIcs.STACS.2022.4"},{"key":"8_CR5","doi-asserted-by":"publisher","unstructured":"Afshar, R., Goodrich, M.T., Ozel, E.: Efficient exact learning algorithms for road networks and other graphs with bounded clustering degrees. Drops-idn\/v2\/document\/10.4230\/lipics.sea.2022.9 (2022). https:\/\/doi.org\/10.4230\/LIPIcs.SEA.2022.9, https:\/\/drops.dagstuhl.de\/entities\/document\/10.4230\/LIPIcs.SEA.2022.9","DOI":"10.4230\/LIPIcs.SEA.2022.9"},{"key":"8_CR6","unstructured":"Arunachaleswaran, E.R., De, A., Kannan, S.: Reconstructing ultrametric trees from noisy experiments. In: Proceedings of the 34th International Conference on Algorithmic Learning Theory, pp. 82\u2013114. PMLR (2023). https:\/\/proceedings.mlr.press\/v201\/arunachaleswaran23a.html. iSSN: 2640-3498 shortConferenceName: ALT"},{"key":"8_CR7","unstructured":"Assadi, S., Chakrabarty, D., Khanna, S.: Graph connectivity and single element recovery via linear and OR queries (2021). http:\/\/arxiv.org\/abs\/2007.06098, arXiv:2007.06098 [cs]"},{"key":"8_CR8","doi-asserted-by":"publisher","unstructured":"Backstrom, L., Kleinberg, J.: Romantic partnerships and the dispersion of social ties: a network analysis of relationship status on Facebook. In: 17th ACM Conference on Computer Supported Cooperative Work & Social Computing, pp. 831\u2013841. CSCW (2014). https:\/\/doi.org\/10.1145\/2531602.2531642","DOI":"10.1145\/2531602.2531642"},{"key":"8_CR9","doi-asserted-by":"publisher","unstructured":"Bastide, P., Groenland, C.: Optimal distance query reconstruction for graphs without long induced cycles (2024). https:\/\/doi.org\/10.48550\/arXiv.2306.05979, arXiv:2306.05979 [cs]","DOI":"10.48550\/arXiv.2306.05979"},{"key":"8_CR10","doi-asserted-by":"publisher","unstructured":"Bernstein, A., Bodwin, G., Wein, N.: Are there graphs whose shortest path structure requires large edge weights? Drops-idn\/v2\/document\/10.4230\/lipics.itcs.2024.12 (2024). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2024.12, https:\/\/drops.dagstuhl.de\/entities\/document\/10.4230\/LIPIcs.ITCS.2024.12","DOI":"10.4230\/LIPIcs.ITCS.2024.12"},{"key":"8_CR11","doi-asserted-by":"publisher","unstructured":"Bu, F., Kang, S., Shin, K.: Interplay between topology and edge weights in real-world graphs: concepts, patterns, and an algorithm. Data Min. Knowl. Discov. 37(6), 2139\u20132191 (2023). https:\/\/doi.org\/10.1007\/s10618-023-00940-w","DOI":"10.1007\/s10618-023-00940-w"},{"key":"8_CR12","doi-asserted-by":"publisher","unstructured":"Chen, C., Hwang, F.: Detecting and locating electrical shorts using group testing. IEEE Trans. Circuits Syst. 36(8), 1113\u20131116 (1989). https:\/\/doi.org\/10.1109\/31.192423, http:\/\/ieeexplore.ieee.org\/document\/192423\/","DOI":"10.1109\/31.192423"},{"key":"8_CR13","unstructured":"Choi, S.S.: Polynomial time optimal query algorithms for finding graphs with arbitrary real weights. In: Proceedings of the 26th Annual Conference on Learning Theory, pp. 797\u2013818. PMLR (2013). https:\/\/proceedings.mlr.press\/v30\/Choi13.html. iSSN 1938-7228"},{"key":"8_CR14","doi-asserted-by":"publisher","unstructured":"Culberson, J.C., Rudnicki, P.: A fast algorithm for constructing trees from distance matrices. Inf. Process. Lett. 30(4), 215\u2013220 (1989). https:\/\/doi.org\/10.1016\/0020-0190(89)90216-0, https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0020019089902160","DOI":"10.1016\/0020-0190(89)90216-0"},{"key":"8_CR15","doi-asserted-by":"publisher","unstructured":"Fang, S.C.: Detecting electrical shorts on printed circuit boards. Int. J. Prod. Res. 28(6), 1031\u20131037 (1990). https:\/\/doi.org\/10.1080\/00207549008942773, https:\/\/www.tandfonline.com\/doi\/full\/10.1080\/00207549008942773","DOI":"10.1080\/00207549008942773"},{"key":"8_CR16","doi-asserted-by":"publisher","unstructured":"Foucquier, J., Guedj, M.: Analysis of drug combinations: current methodological landscape. Pharmacol. Res. Perspect. 3(3), e00149 (2015). https:\/\/doi.org\/10.1002\/prp2.149, https:\/\/bpspubs.onlinelibrary.wiley.com\/doi\/abs\/10.1002\/prp2.149","DOI":"10.1002\/prp2.149"},{"key":"8_CR17","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/978-3-642-40935-6_14","volume-title":"Algorithmic Learning Theory","author":"M Jagadish","year":"2013","unstructured":"Jagadish, M., Sen, A.: Learning a bounded-degree tree using separator queries. In: Jain, S., Munos, R., Stephan, F., Zeugmann, T. (eds.) Algorithmic Learning Theory, pp. 188\u2013202. Springer, Heidelberg (2013)"},{"key":"8_CR18","unstructured":"Janson, S., Luczak, T., Rucinski, A.: Random Graphs. Wiley (2011). Google-Books-ID: RjnqVoB4VmUC"},{"key":"8_CR19","doi-asserted-by":"publisher","unstructured":"Kannan, S., Mathieu, C., Zhou, H.: Graph reconstruction and verification. ACM Trans. Algorithms 14(4), 1\u201330 (2018). https:\/\/doi.org\/10.1145\/3199606, https:\/\/dl.acm.org\/doi\/10.1145\/3199606","DOI":"10.1145\/3199606"},{"key":"8_CR20","unstructured":"Kim, J.H.: Finding weighted graphs by combinatorial search. Arxiv abs\/1201.3793 (2012). https:\/\/www.semanticscholar.org\/paper\/6ff61e772de7d2a649c5979ea239bd26b375ec01, arXiv:1201.3793 [cs, math]"},{"key":"8_CR21","doi-asserted-by":"publisher","unstructured":"Krivelevich, M., Zhukovskii, M.: Reconstructing random graphs from distance queries (2024). https:\/\/doi.org\/10.48550\/arXiv.2404.18318, arXiv:2404.18318 [math]","DOI":"10.48550\/arXiv.2404.18318"},{"key":"8_CR22","doi-asserted-by":"publisher","unstructured":"Kumar, R., Liu, P., Charikar, M., Benson, A.R.: Retrieving top weighted triangles in graphs. In: Proceedings of the 13th International Conference on Web Search and Data Mining, WSDM 2020, pp. 295\u2013303. ACM, Houston (2020). https:\/\/doi.org\/10.1145\/3336191.3371823, https:\/\/dl.acm.org\/doi\/10.1145\/3336191.3371823","DOI":"10.1145\/3336191.3371823"},{"key":"8_CR23","unstructured":"Liu, X., Mukherjee, S.: Tight query complexity bounds for learning graph partitions. In: Proceedings of Thirty Fifth Conference on Learning Theory, pp. 167\u2013181. PMLR (2022). https:\/\/proceedings.mlr.press\/v178\/liu22a.html. iSSN 2640-3498"},{"key":"8_CR24","doi-asserted-by":"publisher","unstructured":"Mathieu, C., Zhou, H.: A simple algorithm for graph reconstruction. Drops-idn\/v2\/document\/10.4230\/lipics.esa.2021.68 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2021.68, https:\/\/drops.dagstuhl.de\/entities\/document\/10.4230\/LIPIcs.ESA.2021.68","DOI":"10.4230\/LIPIcs.ESA.2021.68"},{"key":"8_CR25","doi-asserted-by":"publisher","unstructured":"Mazzawi, H.: Optimally reconstructing weighted graphs using queries: (extended abstract). In: Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 608\u2013615. Proceedings, Society for Industrial and Applied Mathematics (2010). https:\/\/doi.org\/10.1137\/1.9781611973075.51, https:\/\/epubs.siam.org\/doi\/10.1137\/1.9781611973075.51","DOI":"10.1137\/1.9781611973075.51"},{"key":"8_CR26","doi-asserted-by":"publisher","unstructured":"Shi, W., West, D.B.: Diagnosis of wiring networks: an optimal randomized algorithm for finding connected components of unknown graphs. SIAM J. Comput. 28(5), 1541\u20131551 (1999). https:\/\/doi.org\/10.1137\/S0097539795288118, http:\/\/epubs.siam.org\/doi\/10.1137\/S0097539795288118","DOI":"10.1137\/S0097539795288118"},{"key":"8_CR27","doi-asserted-by":"publisher","unstructured":"Shi, W., West, D.B.: Structural diagnosis of wiring networks: finding connected components of unknown subgraphs. SIAM J. Discrete Math. 14(4), 510\u2013523 (2001). https:\/\/doi.org\/10.1137\/S0895480100371286, http:\/\/epubs.siam.org\/doi\/10.1137\/S0895480100371286","DOI":"10.1137\/S0895480100371286"},{"issue":"1","key":"8_CR28","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1093\/sf\/sov079","volume":"94","author":"C Stadtfeld","year":"2015","unstructured":"Stadtfeld, C., Pentland, A.S.: Partnership ties shape friendship networks: a dynamic social network study. Soc. Forces 94(1), 453\u2013477 (2015). https:\/\/doi.org\/10.1093\/sf\/sov079","journal-title":"Soc. Forces"},{"key":"8_CR29","doi-asserted-by":"publisher","unstructured":"Stegehuis, C., Weedage, L.: Reconstruction of geometric random graphs with the simple algorithm. Arxiv abs\/2407.18591 (2024). https:\/\/doi.org\/10.48550\/arXiv.2407.18591, https:\/\/www.semanticscholar.org\/paper\/0487c10a7522b6cc483b7e7c6e2821b31bf581bd, arXiv:2407.18591 [cs, math]","DOI":"10.48550\/arXiv.2407.18591"},{"key":"8_CR30","unstructured":"Wang, Z., Honorio, J.: Reconstructing a bounded-degree directed tree using path queries (2017). https:\/\/arxiv.org\/abs\/1606.05183"},{"key":"8_CR31","doi-asserted-by":"publisher","unstructured":"Yang, S.H., Smola, A.J., Long, B., Zha, H., Chang, Y.: Friend or frenemy? Predicting signed ties in social networks. In: 35th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 555\u2013564. SIGIR (2012). https:\/\/doi.org\/10.1145\/2348283.2348359","DOI":"10.1145\/2348283.2348359"}],"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-031-98740-3_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T13:57:34Z","timestamp":1784383054000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-98740-3_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031987397","9783031987403"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-98740-3_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"18 July 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","label":"Disclosure of Interests","group":{"name":"EthicsHeading","label":"Ethics"}},{"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":"Bozeman, MT","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 July 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 July 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"36","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.cs.montana.edu\/bhz\/iwoca2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}