{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:18:57Z","timestamp":1759637937656,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,3,4]],"date-time":"2022-03-04T00:00:00Z","timestamp":1646352000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004329","name":"Slovenian Research Agency","doi-asserted-by":"crossref","award":["program P1-0297 and projects J1-9109, J1-8130, J1-8155, J1-1693, J1-2452"],"award-info":[{"award-number":["program P1-0297 and projects J1-9109, J1-8130, J1-8155, J1-1693, J1-2452"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,4,30]]},"abstract":"<jats:p>\n            The inverse geodesic length of a graph\n            <jats:italic>G<\/jats:italic>\n            is the sum of the inverse of the distances between all pairs of distinct vertices of\n            <jats:italic>G<\/jats:italic>\n            . In some domains, it is known as the Harary index or the global efficiency of the graph. We show that, if\n            <jats:italic>G<\/jats:italic>\n            is planar and has\n            <jats:italic>n<\/jats:italic>\n            vertices, then the inverse geodesic length of\n            <jats:italic>G<\/jats:italic>\n            can be computed in roughly\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>9\/5<\/jats:sup>\n            ) time. We also show that, if\n            <jats:italic>G<\/jats:italic>\n            has\n            <jats:italic>n<\/jats:italic>\n            vertices and treewidth at most\n            <jats:italic>k<\/jats:italic>\n            , then the inverse geodesic length of\n            <jats:italic>G<\/jats:italic>\n            can be computed in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>k<\/jats:italic>\n              )\n            <\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) time. In both cases, we use techniques developed for computing the sum of the distances, which does not have \u201cinverse\u201d component, together with batched evaluations of rational functions.\n          <\/jats:p>","DOI":"10.1145\/3501303","type":"journal-article","created":{"date-parts":[[2022,3,4]],"date-time":"2022-03-04T11:32:35Z","timestamp":1646393555000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Computing the Inverse Geodesic Length in Planar Graphs and Graphs of Bounded Treewidth"],"prefix":"10.1145","volume":"18","author":[{"given":"Sergio","family":"Cabello","sequence":"first","affiliation":[{"name":"University of Ljubljana, Slovenia and Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,3,4]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch28"},{"key":"e_1_3_3_3_2","first-page":"1","volume-title":"Advances in Discrete and Computational Geometry","author":"Agarwal Pankaj K.","year":"1998","unstructured":"Pankaj K. Agarwal and Jeff Erickson. 1998. Geometric range searching and its relatives. In Advances in Discrete and Computational Geometry, B. Chazelle, J. Goodman, and R. Pollack (Eds.). AMS, 1\u201356."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3209678"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/130947374"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00680-z"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3218821"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2009.02.001"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_3_3_12_2","volume-title":"Topological Indices and Related Descriptors in QSAR and QSPR","author":"Devillers James","year":"1999","unstructured":"James Devillers and Alexandru T. Balaban (Eds.). 1999. Topological Indices and Related Descriptors in QSAR and QSPR. CRC Press."},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.05.007"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102788"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ISAAC.2019.59"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1193402"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1493"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488672"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009223"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.87.198701"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1140\/epjb\/e2003-00095-5"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90005-X"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2847257"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01164638"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488673"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.5555\/2512973"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3501303","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3501303","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:19Z","timestamp":1750188619000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3501303"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,4]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4,30]]}},"alternative-id":["10.1145\/3501303"],"URL":"https:\/\/doi.org\/10.1145\/3501303","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2022,3,4]]},"assertion":[{"value":"2019-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}