{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:22:17Z","timestamp":1753885337301,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476710"},{"type":"electronic","value":"9783662476727"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_63","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"773-784","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Near-Linear Query Complexity for Graph Inference"],"prefix":"10.1007","author":[{"given":"Sampath","family":"Kannan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Claire","family":"Mathieu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hang","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"issue":"4","key":"63_CR1","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1145\/1538902.1538905","volume":"56","author":"D Achlioptas","year":"2009","unstructured":"Achlioptas, D., Clauset, A., Kempe, D., Moore, C.: On the bias of traceroute sampling: or, power-law degree distributions in regular graphs. Journal of the ACM (JACM) 56(4), 21 (2009)","journal-title":"Journal of the ACM (JACM)"},{"key":"63_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/11604686_12","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"Z Beerliova","year":"2005","unstructured":"Beerliova, Z., Eberhard, F., Erlebach, T., Hall, A., Hoffmann, M., Miha\u013e\u00e1k, M., Shankar Ram, L.: Network discovery and verification. In: Kratsch, D. (ed.) WG 2005. LNCS, vol. 3787, pp. 127\u2013138. Springer, Heidelberg (2005)"},{"key":"63_CR3","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1214\/088342304000000422","volume":"19","author":"R Castro","year":"2004","unstructured":"Castro, R., Coates, M., Liang, G., Nowak, R., Yu, B.: Network tomography: recent developments. Statistical Science 19, 499\u2013517 (2004)","journal-title":"Statistical Science"},{"key":"63_CR4","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1006\/jcss.2001.1785","volume":"63","author":"F Chung","year":"2001","unstructured":"Chung, F., Garrett, M., Graham, R., Shallcross, D.: Distance realization problems with applications to internet tomography. Journal of Computer and System Sciences 63, 432\u2013448 (2001)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"63_CR5","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1016\/j.tcs.2005.12.009","volume":"355","author":"L Dall\u2019Asta","year":"2006","unstructured":"Dall\u2019Asta, L., Alvarez-Hamelin, I., Barrat, A., V\u00e1zquez, A., Vespignani, A.: Exploring networks with traceroute-like probes: Theory and simulations. Theoretical Computer Science 355(1), 6\u201324 (2006)","journal-title":"Theoretical Computer Science"},{"key":"63_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/11758471_10","volume-title":"Algorithms and Complexity","author":"T Erlebach","year":"2006","unstructured":"Erlebach, T., Hall, A., Hoffmann, M., Miha\u013e\u00e1k, M.: Network discovery and verification with distance queries. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds.) CIAC 2006. LNCS, vol. 3998, pp. 69\u201380. Springer, Heidelberg (2006)"},{"issue":"5","key":"63_CR7","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/BF02459968","volume":"51","author":"JJ Hein","year":"1989","unstructured":"Hein, J.J.: An optimal algorithm to reconstruct trees from additive distance data. Bulletin of Mathematical Biology 51(5), 597\u2013603 (1989)","journal-title":"Bulletin of Mathematical Biology"},{"issue":"3","key":"63_CR8","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. Journal of computer and system sciences 9(3), 256\u2013278 (1974)","journal-title":"Journal of computer and system sciences"},{"key":"63_CR9","unstructured":"King, V., Zhang, L., Zhou, Y.: On the complexity of distance-based evolutionary tree reconstruction. In: SODA, pp. 444\u2013453. SIAM (2003)"},{"key":"63_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1007\/978-3-642-39206-1_62","volume-title":"Automata, Languages, and Programming","author":"C Mathieu","year":"2013","unstructured":"Mathieu, C., Zhou, H.: Graph reconstruction via distance oracles. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 733\u2013744. Springer, Heidelberg (2013)"},{"issue":"3","key":"63_CR11","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.ipl.2006.08.013","volume":"101","author":"L Reyzin","year":"2007","unstructured":"Reyzin, L., Srivastava, N.: On the longest path algorithm for reconstructing trees from distance matrices. Information processing letters 101(3), 98\u2013100 (2007)","journal-title":"Information processing letters"},{"key":"63_CR12","doi-asserted-by":"crossref","unstructured":"Tarissan, F., Latapy, M., Prieur, C.: Efficient measurement of complex networks using link queries. In: INFOCOM Workshops, pp. 254\u2013259. IEEE (2009)","DOI":"10.1109\/INFCOMW.2009.5072135"},{"key":"63_CR13","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: Symposium on Parallel Algorithms and Architectures, pp. 1\u201310. ACM (2001)","DOI":"10.1145\/378580.378581"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_63","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T12:46:48Z","timestamp":1676638008000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_63"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_63","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}