{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T19:12:32Z","timestamp":1743102752141,"version":"3.40.3"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319487489"},{"type":"electronic","value":"9783319487496"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-48749-6_24","type":"book-chapter","created":{"date-parts":[[2016,10,30]],"date-time":"2016-10-30T04:16:59Z","timestamp":1477801019000},"page":"326-339","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound"],"prefix":"10.1007","author":[{"given":"Sung Eun","family":"Bae","sequence":"first","affiliation":[]},{"given":"Tong-Wook","family":"Shinn","sequence":"additional","affiliation":[]},{"given":"Tadao","family":"Takaoka","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,10,31]]},"reference":[{"key":"24_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"AV Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Boston (1974)"},{"key":"24_CR2","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1142\/S0218195993000282","volume":"3","author":"MJ Atallah","year":"1993","unstructured":"Atallah, M.J., Callahan, P.B., Goodrich, M.T.: P-complete geometric problems. Int. J. Comput. Geom. Appl. 3, 443\u2013462 (1993)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"24_CR3","unstructured":"Alon, N., Galil, Z., Margalit, O.: On the exponent of the all pairs shortest path problem. In: FOCS, pp. 569\u2013575 (1991)"},{"key":"24_CR4","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/s00453-007-9062-1","volume":"2","author":"TM Chan","year":"2008","unstructured":"Chan, T.M.: All-pairs shortest paths with real weights in \n                      \n                        \n                      \n                      $$O(n^{3}\/\\log {n})$$\n                     time. Algorithmica 2, 236\u2013243 (2008)","journal-title":"Algorithmica"},{"key":"24_CR5","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1080\/00207169008803814","volume":"32","author":"W Dobosiewicz","year":"1990","unstructured":"Dobosiewicz, W.: A more efficient algorithm for the min-plus multiplication. Int. J. Comput. Math. 32, 49\u201360 (1990)","journal-title":"Int. J. Comput. Math."},{"issue":"6","key":"24_CR6","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"RW Floyd","year":"1962","unstructured":"Floyd, R.W.: Algorithm 97: shortest path. Commun. ACM 5(6), 345 (1962)","journal-title":"Commun. ACM"},{"key":"24_CR7","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1137\/0205006","volume":"5","author":"ML Fredman","year":"1976","unstructured":"Fredman, M.L.: New bounds on the complexity of the shortest path problem. SIAM J. Comput. 5, 83\u201389 (1976)","journal-title":"SIAM J. Comput."},{"key":"24_CR8","unstructured":"Gilbert, P.D.: New results on planar triangulations. Report R-850, Coordinated Science Laboratory, University of Illinois, Urbana, Illinois (1979)"},{"key":"24_CR9","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/j.ipl.2004.05.006","volume":"91","author":"Y Han","year":"2004","unstructured":"Han, Y.: Improved algorithm for all pairs shortest paths. Inf. Process. Lett. 91, 245\u2013250 (2004)","journal-title":"Inf. Process. Lett."},{"key":"24_CR10","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1007\/s00453-007-9063-0","volume":"51","author":"Y Han","year":"2008","unstructured":"Han, Y.: An \n                      \n                        \n                      \n                      $$O(n^{3}(\\log {\\log {n}}\/\\log {n})^{5\/4})$$\n                     time algorithm for all pairs shortest path. Algorithmica 51, 428\u2013434 (2008)","journal-title":"Algorithmica"},{"key":"24_CR11","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 \n                      \n                        \n                      \n                      $$O(n^{3}\\log {\\log {n}}\/\\log ^{2}{n})$$\n                     time algorithm for all pairs shortest paths. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol. 7357, pp. 131\u2013141. Springer, Heidelberg (2012)"},{"key":"24_CR12","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/S0167-5060(08)70044-X","volume":"9","author":"GT Klincsek","year":"1980","unstructured":"Klincsek, G.T.: Minimal triangulations of polygonal domains. Ann. Discret. Math. 9, 121\u2013123 (1980)","journal-title":"Ann. Discret. Math."},{"key":"24_CR13","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1006\/jcss.1995.1078","volume":"51","author":"R Seidel","year":"1995","unstructured":"Seidel, R.: On the all-pairs-shortest-path problem in unweighted undirected graphs. J. Comput. Syst. Sci. 51, 400\u2013403 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"24_CR14","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0020-0190(92)90200-F","volume":"43","author":"T Takaoka","year":"1992","unstructured":"Takaoka, T.: A new upper bound on the complexity of the all pairs shortest path problem. Inf. Process. Lett. 43, 195\u2013199 (1992)","journal-title":"Inf. Process. Lett."},{"key":"24_CR15","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.ipl.2005.08.008","volume":"96","author":"T Takaoka","year":"2005","unstructured":"Takaoka, T.: An \n                      \n                        \n                      \n                      $$O(n^{3}\\log {\\log {n}}\/\\log {n})$$\n                     time algorithm for the all-pairs shortest path problem. Inf. Process. Lett. 96, 155\u2013161 (2005)","journal-title":"Inf. Process. Lett."},{"key":"24_CR16","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1145\/567112.567114","volume":"49","author":"U Zwick","year":"2002","unstructured":"Zwick, U.: All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM 49, 289\u2013317 (2002)","journal-title":"J. ACM"},{"key":"24_CR17","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s00453-005-1199-1","volume":"46","author":"U Zwick","year":"2006","unstructured":"Zwick, U.: A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths. Algorithmica 46, 181\u2013192 (2006)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-48749-6_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T22:19:15Z","timestamp":1558477155000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-48749-6_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319487489","9783319487496"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-48749-6_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"31 October 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hong Kong","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 December 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 December 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conference.cs.cityu.edu.hk\/cocoa2016\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}