{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:20:43Z","timestamp":1759638043884},"publisher-location":"Berlin, Heidelberg","reference-count":20,"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_70","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T17:20:16Z","timestamp":1372785616000},"page":"828-839","source":"Crossref","is-referenced-by-count":1,"title":["Approximating the Diameter of Planar Graphs in Near Linear Time"],"prefix":"10.1007","author":[{"given":"Oren","family":"Weimann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raphael","family":"Yuster","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"70_CR1","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1137\/S0097539796303421","volume":"28","author":"D. Aingworth","year":"1999","unstructured":"Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM Journal on Computing\u00a028(4), 1167\u20131181 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"70_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1007\/978-3-540-73951-7_47","volume-title":"Algorithms and Data Structures","author":"P. Berman","year":"2007","unstructured":"Berman, P., Kasiviswanathan, S.P.: Faster approximation of distances in graphs. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol.\u00a04619, pp. 541\u2013552. Springer, Heidelberg (2007)"},{"key":"70_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/11764298_9","volume-title":"Experimental Algorithms","author":"K. Boitmanis","year":"2006","unstructured":"Boitmanis, K., Freivalds, K., Ledi\u0146\u0161, P., Opmanis, R.: Fast and simple approximation of the diameter and radius of a graph. In: \u00c0lvarez, C., Serna, M. (eds.) WEA 2006. LNCS, vol.\u00a04007, pp. 98\u2013108. Springer, Heidelberg (2006)"},{"key":"70_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/BFb0049406","volume-title":"Algorithms - ESA \u201994","author":"V. Chepoi","year":"1994","unstructured":"Chepoi, V., Dragan, F.F.: A linear-time algorithm for finding a central vertex of a chordal graph. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol.\u00a0855, pp. 159\u2013170. Springer, Heidelberg (1994)"},{"key":"70_CR5","first-page":"295","volume":"60","author":"F.R.K. Chung","year":"1987","unstructured":"Chung, F.R.K.: Diameters of graphs: Old problems and new results. Congressus Numerantium\u00a060, 295\u2013317 (1987)","journal-title":"Congressus Numerantium"},{"key":"70_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1007\/3-540-62559-3_15","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"F.F. Dragan","year":"1997","unstructured":"Dragan, F.F., Nicolai, F., Brandstadt, A.: LexBFS-orderings and powers of graphs. In: D\u2019Amore, F., Marchetti-Spaccamela, A., Franciosa, P.G. (eds.) WG 1996. LNCS, vol.\u00a01197, pp. 166\u2013180. Springer, Heidelberg (1997)"},{"unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. In: Proc. of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 632\u2013640 (1995)","key":"70_CR7"},{"key":"70_CR8","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0166-218X(80)90039-6","volume":"2","author":"A.M. Farley","year":"1980","unstructured":"Farley, A.M., Proskurowski, A.: Computation of the center and diameter of outerplanar graphs. Discrete Applied Mathematics\u00a02, 185\u2013191 (1980)","journal-title":"Discrete Applied Mathematics"},{"key":"70_CR9","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"G.N. Frederickson","year":"1987","unstructured":"Frederickson, G.N.: Fast algorithms for shortest paths in planar graphs. SIAM Journal on Computing\u00a016, 1004\u20131022 (1987)","journal-title":"SIAM Journal on Computing"},{"key":"70_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/978-3-642-31155-0_12","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"Y. Han","year":"2012","unstructured":"Han, Y., Takaoka, T.: An O(n\n                  3 loglogn\/log2\n                  n) time algorithm for all pairs shortest paths. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol.\u00a07357, pp. 131\u2013141. Springer, Heidelberg (2012)"},{"issue":"3","key":"70_CR11","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1137\/S0895480190177042","volume":"7","author":"D. Hartvigsen","year":"1994","unstructured":"Hartvigsen, D., Mardon, R.: The all-pairs min cut problem and the minimum cycle basis problem on planar graphs. Journal of Discrete Mathematics\u00a07(3), 403\u2013418 (1994)","journal-title":"Journal of Discrete Mathematics"},{"issue":"1","key":"70_CR12","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1006\/jcss.1997.1493","volume":"55","author":"M.R. Henzinger","year":"1997","unstructured":"Henzinger, M.R., Klein, P.N., Rao, S., Subramanian, S.: Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences\u00a055(1), 3\u201323 (1997)","journal-title":"Journal of Computer and System Sciences"},{"key":"70_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/321992.321993","volume":"24","author":"D.B. Johnson","year":"1977","unstructured":"Johnson, D.B.: Efficient algorithms for shortest paths in sparse graphs. Journal of the ACM\u00a024, 1\u201313 (1977)","journal-title":"Journal of the ACM"},{"unstructured":"Klein, P.N.: Multiple-source shortest paths in planar graphs. In: Proc. of the 16th Annual ACM-SIAM Symposium on Discrete Mathematics (SODA), pp. 146\u2013155 (2005)","key":"70_CR14"},{"unstructured":"Klein, P.N.: Preprocessing an undirected planar network to enable fast approximate distance queries. In: Proc. of the 13th Annual ACM-SIAM Symposium on Discrete Mathematics (SODA), pp. 820\u2013827 (2002)","key":"70_CR15"},{"key":"70_CR16","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM Journal on Applied Math.\u00a036, 177\u2013189 (1979)","journal-title":"SIAM Journal on Applied Math."},{"key":"70_CR17","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1080\/00207169008803870","volume":"34","author":"S. Olariu","year":"1990","unstructured":"Olariu, S.: A simple linear-time algorithm for computing the center of an interval graph. International Journal of Computer Mathematics\u00a034, 121\u2013128 (1990)","journal-title":"International Journal of Computer Mathematics"},{"key":"70_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/3-540-45465-9_9","volume-title":"Automata, Languages and Programming","author":"S. Pettie","year":"2002","unstructured":"Pettie, S.: A faster all-pairs shortest path algorithm for real-weighted sparse graphs. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 85\u201397. Springer, Heidelberg (2002)"},{"issue":"6","key":"70_CR19","doi-asserted-by":"crossref","first-page":"993","DOI":"10.1145\/1039488.1039493","volume":"51","author":"M. Thorup","year":"2004","unstructured":"Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. Journal of the ACM\u00a051(6), 993\u20131024 (2004); Announced at FOCS 2001","journal-title":"Journal of the ACM"},{"unstructured":"Wulff-Nilsen, C.: Wiener index, diameter, and stretch factor of a weighted planar graph in subquadratic time. Technical report, University of Copenhagen (2008)","key":"70_CR20"}],"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_70","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T09:07:31Z","timestamp":1557911251000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39206-1_70"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392054","9783642392061"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39206-1_70","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}