{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T18:27:13Z","timestamp":1778783233358,"version":"3.51.4"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,8,9]],"date-time":"2018-08-09T00:00:00Z","timestamp":1533772800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"French Agence Nationale de la Recherche","award":["ANR-12-BS02-005 (RDAM project)"],"award-info":[{"award-number":["ANR-12-BS02-005 (RDAM project)"]}]},{"name":"Lise Meitner Award Fellowship"},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["NRI 1317788"],"award-info":[{"award-number":["NRI 1317788"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,10,31]]},"abstract":"<jats:p>\n            How efficiently can we find an unknown graph using distance or shortest path queries between its vertices? We assume that the unknown graph\n            <jats:italic>G<\/jats:italic>\n            is connected, unweighted, and has bounded degree. In the\n            <jats:italic>reconstruction<\/jats:italic>\n            problem, the goal is to find the graph\n            <jats:italic>G<\/jats:italic>\n            . In the\n            <jats:italic>verification<\/jats:italic>\n            problem, we are given a hypothetical graph\n            <jats:italic>\u011c<\/jats:italic>\n            and want to check whether\n            <jats:italic>G<\/jats:italic>\n            is equal to\n            <jats:italic>\u011c<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            We provide a randomized algorithm for reconstruction using \u00d5(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3\/2<\/jats:sup>\n            ) distance queries, based on Voronoi cell decomposition. Next, we analyze natural greedy algorithms for reconstruction using a shortest path oracle and also for verification using either oracle, and show that their query complexity is\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              1+\n              <jats:italic>o<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            . We further improve the query complexity when the graph is chordal or outerplanar. Finally, we show some lower bounds, and consider an approximate version of the reconstruction problem.\n          <\/jats:p>","DOI":"10.1145\/3199606","type":"journal-article","created":{"date-parts":[[2018,8,13]],"date-time":"2018-08-13T12:29:41Z","timestamp":1534163381000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Graph Reconstruction and Verification"],"prefix":"10.1145","volume":"14","author":[{"given":"Sampath","family":"Kannan","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Claire","family":"Mathieu","sequence":"additional","affiliation":[{"name":"\u00c9cole Normale Sup\u00e9rieure, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hang","family":"Zhou","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique, Palaiseau, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,8,9]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"33rd Symposium on Theoretical Aspects of Computer Science (STACS'16)","volume":"47","author":"Abrahamsen Mikkel","year":"2016","unstructured":"Mikkel Abrahamsen, Greg Bodwin, Eva Rotenberg, and Morten St\u00f6ckel. 2016. Graph reconstruction with a betweenness oracle. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS'16), Nicolas Ollinger and Heribert Vollmer (Eds.). Vol. 47. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538902.1538905"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2006.884015"},{"key":"e_1_2_1_4_1","volume-title":"Blair and Barry Peyton","author":"Jean R.","year":"1993","unstructured":"Jean R. S. Blair and Barry Peyton. 1993. An introduction to chordal graphs and clique trees. In Graph Theory and Sparse Matrix Computation. Springer, 1--29."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1214\/088342304000000422"},{"key":"e_1_2_1_6_1","first-page":"433","article-title":"Planar permutation graphs. Ann. l\u2019Institut Henri Poincar\u00e9 (B) Prob","volume":"3","author":"Chartrand Gary","year":"1967","unstructured":"Gary Chartrand and Frank Harary. 1967. Planar permutation graphs. Ann. l\u2019Institut Henri Poincar\u00e9 (B) Prob. Statist. 3, 4 (1967), 433--438.","journal-title":"Statist."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1785"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.12.009"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02459968"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISVD.2009.26"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"e_1_2_1_12_1","volume-title":"International Colloquium on Automata, Languages and Programming","author":"Kannan Sampath","unstructured":"Sampath Kannan, Claire Mathieu, and Hang Zhou. 2015. Near-linear query complexity for graph inference. In International Colloquium on Automata, Languages and Programming. Springer, 773--784."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644179"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_62"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275671"},{"key":"e_1_2_1_16_1","volume-title":"Recent Advances in Algorithms and Combinatorics","author":"Reed Bruce A.","unstructured":"Bruce A. Reed. 2003. Algorithmic aspects of tree width. In Recent Advances in Algorithms and Combinatorics. Springer, 85--107."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75225-7_24"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11440-3_21"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1719850.1719893"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378581"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-5193(77)90351-4"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3199606","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3199606","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3199606","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:07:18Z","timestamp":1750273638000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3199606"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,9]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,10,31]]}},"alternative-id":["10.1145\/3199606"],"URL":"https:\/\/doi.org\/10.1145\/3199606","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,9]]},"assertion":[{"value":"2017-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}