{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T13:58:52Z","timestamp":1753883932744,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642392054"},{"type":"electronic","value":"9783642392061"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39206-1_62","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T13:20:16Z","timestamp":1372771216000},"page":"733-744","source":"Crossref","is-referenced-by-count":5,"title":["Graph Reconstruction via Distance Oracles"],"prefix":"10.1007","author":[{"given":"Claire","family":"Mathieu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hang","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"62_CR1","doi-asserted-by":"crossref","unstructured":"Amenta, N., Bern, M., Eppstein, D.: The crust and the beta-skeleton: Combinatorial curve reconstruction. In: Graphical Models and Image Processing, pp. 125\u2013135 (1998)","DOI":"10.1006\/gmip.1998.0465"},{"key":"62_CR2","doi-asserted-by":"crossref","unstructured":"Anandkumar, A., Hassidim, A., Kelner, J.A.: Topology discovery of sparse random graphs with few participants. In: SIGMETRICS, pp. 293\u2013304. ACM (2011)","DOI":"10.1145\/1993744.1993774"},{"key":"62_CR3","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/978-3-540-27819-1_15","volume-title":"Learning Theory","author":"D. Angluin","year":"2004","unstructured":"Angluin, D., Chen, J.: Learning a hidden graph using O(log n) queries per edge. In: Learning Theory, pp. 210\u2013223. Springer, Heidelberg (2004)"},{"key":"62_CR4","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., Ram, L.S.: Network discovery and verification. In: Kratsch, D. (ed.) WG 2005. LNCS, vol.\u00a03787, pp. 127\u2013138. Springer, Heidelberg (2005)"},{"key":"62_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/11604686_2","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M. Bouvel","year":"2005","unstructured":"Bouvel, M., Grebinski, V., Kucherov, G.: Combinatorial search on graphs motivated by bioinformatics applications: A brief survey. In: Kratsch, D. (ed.) WG 2005. LNCS, vol.\u00a03787, pp. 16\u201327. Springer, Heidelberg (2005)"},{"key":"62_CR6","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\u00a019, 499\u2013517 (2004)","journal-title":"Statistical Science"},{"issue":"4","key":"62_CR7","first-page":"433","volume":"3","author":"G. Chartrand","year":"1967","unstructured":"Chartrand, G., Harary, F.: Planar permutation graphs. Annales de l\u2019institut Henri Poincar\u00e9 (B) Probabilit\u00e9s et Statistiques\u00a03(4), 433\u2013438 (1967)","journal-title":"Annales de l\u2019institut Henri Poincar\u00e9 (B) Probabilit\u00e9s et Statistiques"},{"key":"62_CR8","doi-asserted-by":"crossref","unstructured":"Chen, D., Guibas, L.J., Hershberger, J., Sun, J.: Road network reconstruction for organizing paths. In: SODA, pp. 1309\u20131320 (2010)","DOI":"10.1137\/1.9781611973075.105"},{"key":"62_CR9","doi-asserted-by":"crossref","unstructured":"Choi, S.-S., Kim, J.H.: Optimal query complexity bounds for finding graphs. In: STOC, pp. 749\u2013758. ACM (2008)","DOI":"10.1145\/1374376.1374484"},{"issue":"1","key":"62_CR10","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\u00a0355(1), 6\u201324 (2006)","journal-title":"Theoretical Computer Science"},{"key":"62_CR11","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/S0925-7721(01)00015-3","volume":"19","author":"T.K. Dey","year":"2000","unstructured":"Dey, T.K., Wenger, R.: Reconstructing curves with sharp corners. Comput. Geom. Theory and Appl.\u00a019, 89\u201399 (2000)","journal-title":"Comput. Geom. Theory and Appl."},{"key":"62_CR12","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.\u00a03998, pp. 69\u201380. Springer, Heidelberg (2006)"},{"issue":"1","key":"62_CR13","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/s004530010033","volume":"28","author":"V. Grebinski","year":"2000","unstructured":"Grebinski, V., Kucherov, G.: Optimal reconstruction of graphs under the additive model. Algorithmica\u00a028(1), 104\u2013124 (2000)","journal-title":"Algorithmica"},{"issue":"5","key":"62_CR14","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1007\/BF02459968","volume":"51","author":"J.J. Hein","year":"1989","unstructured":"Hein, J.J.: An optimal algorithm to reconstruct trees from additive distance data. Bulletin of Mathematical Biology\u00a051(5), 597\u2013603 (1989)","journal-title":"Bulletin of Mathematical Biology"},{"key":"62_CR15","doi-asserted-by":"crossref","unstructured":"Honiden, S., Houle, M.E., Sommer, C.: Balancing graph voronoi diagrams. In: ISVD, pp. 183\u2013191. IEEE (2009)","DOI":"10.1109\/ISVD.2009.26"},{"key":"62_CR16","unstructured":"King, V., Zhang, L., Zhou, Y.: On the complexity of distance-based evolutionary tree reconstruction. In: SODA, pp. 444\u2013453. SIAM (2003)"},{"key":"62_CR17","doi-asserted-by":"crossref","unstructured":"Mazzawi, H.: Optimally reconstructing weighted graphs using queries. In: SODA, pp. 608\u2013615. SIAM (2010)","DOI":"10.1137\/1.9781611973075.51"},{"key":"62_CR18","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/978-3-540-75225-7_24","volume-title":"Algorithmic Learning Theory","author":"L. Reyzin","year":"2007","unstructured":"Reyzin, L., Srivastava, N.: Learning and verifying graphs using queries with a focus on edge counting. In: Hutter, M., Servedio, R.A., Takimoto, E. (eds.) ALT 2007. LNCS (LNAI), vol.\u00a04754, pp. 285\u2013297. Springer, Heidelberg (2007), \n                    \n                      http:\/\/dx.doi.org\/10.1007\/978-3-540-75225-7_24"},{"issue":"3","key":"62_CR19","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\u00a0101(3), 98\u2013100 (2007)","journal-title":"Information Processing Letters"},{"key":"62_CR20","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":"62_CR21","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: SPAA, pp. 1\u201310. ACM (2001)","DOI":"10.1145\/378580.378581"},{"issue":"2","key":"62_CR22","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0022-5193(77)90351-4","volume":"64","author":"M.S. Waterman","year":"1977","unstructured":"Waterman, M.S., Smith, T.F., Singh, M., Beyer, W.A.: Additive evolutionary trees. Journal of Theoretical Biology\u00a064(2), 199\u2013213 (1977)","journal-title":"Journal of Theoretical Biology"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39206-1_62","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T05:33:54Z","timestamp":1557898434000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39206-1_62"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392054","9783642392061"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39206-1_62","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}