{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:29:53Z","timestamp":1759638593852,"version":"3.41.0"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2003,3,1]],"date-time":"2003-03-01T00:00:00Z","timestamp":1046476800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2003,3,1]],"date-time":"2003-03-01T00:00:00Z","timestamp":1046476800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Mathematical Modelling and Algorithms"],"published-print":{"date-parts":[[2003,3]]},"DOI":"10.1023\/a:1023695531209","type":"journal-article","created":{"date-parts":[[2003,6,6]],"date-time":"2003-06-06T17:55:35Z","timestamp":1054922135000},"page":"57-65","source":"Crossref","is-referenced-by-count":8,"title":["An Optimal Algorithm to Solve the All-Pairs Shortest Paths Problem on Permutation Graphs"],"prefix":"10.1007","volume":"2","author":[{"given":"Sukumar","family":"Mondal","sequence":"first","affiliation":[]},{"given":"Madhumangal","family":"Pal","sequence":"additional","affiliation":[]},{"given":"Tapan K.","family":"Pal","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"5114272_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. Aho","year":"1974","unstructured":"Aho, A., Hopcroft, J. and Ullman, J.: The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974."},{"issue":"2","key":"5114272_CR2","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1145\/77600.77615","volume":"37","author":"R. K. Ahuja","year":"1990","unstructured":"Ahuja, R. K., Mehlhorn, K., Orlin, J. B. and Tarjan, R. E.: Faster algorithms for the shortest path problem, J. ACM\n37(2) (1990), 213\u2013223.","journal-title":"J. ACM"},{"key":"5114272_CR3","unstructured":"Alon, N., Galil, Z. and Margalit, O.: On the exponent of the all pairs shortest path problem, In: Proc. 32nd IEEE FOCS, IEEE, 1991, pp. 569\u2013575."},{"key":"5114272_CR4","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1016\/0095-8956(90)90136-N","volume":"48","author":"I. Althofer","year":"1990","unstructured":"Althofer, I.: Average distance in undirected graphs and the removal of vertices, J. Combin. Theory Ser. B\n48 (1990), 140\u2013142.","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"5114272_CR5","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1109\/12.663776","volume":"47","author":"M. Barbehenn","year":"1998","unstructured":"Barbehenn, M.: A note on the complexity of Dijkstra's algorithm for graphs with weighted vertices, IEEE Trans. Comput.\n47(2) (1998), 263.","journal-title":"IEEE Trans. Comput."},{"key":"5114272_CR6","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1002\/jgt.3190120309","volume":"12","author":"D. Bienstock","year":"1988","unstructured":"Bienstock, D. and Gyon, E.: Average distance in graphs with removed elements, J. Graph Theory\n12 (1988), 375\u2013390.","journal-title":"J. Graph Theory"},{"key":"5114272_CR7","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1002\/jgt.3190120213","volume":"12","author":"F. R. K. Chung","year":"1988","unstructured":"Chung, F. R. K.: The average distance and independence number, J. Graph Theory\n12 (1988), 229\u2013235.","journal-title":"J. Graph Theory"},{"key":"5114272_CR8","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0166-218X(94)90095-7","volume":"51","author":"P. Dankelmann","year":"1994","unstructured":"Dankelmann, P.: Average distance and independence number, Discrete Appl. Math.\n51 (1994), 75\u201383.","journal-title":"Discrete Appl. Math."},{"key":"5114272_CR9","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/0020-0190(93)90174-8","volume":"48","author":"P. Dankelmann","year":"1993","unstructured":"Dankelmann, P.: Computing the average distance of an interval graphs, Inform. Process. Lett.\n48 (1993), 311\u2013314.","journal-title":"Inform. Process. Lett."},{"key":"5114272_CR10","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. W. Dijkstra","year":"1959","unstructured":"Dijkstra, E. W.: A note on two problems in connexion with graphs, Numer. Math.\n1 (1959), 269\u2013271.","journal-title":"Numer. Math."},{"key":"5114272_CR11","first-page":"121","volume":"64","author":"P. Erdos","year":"1988","unstructured":"Erdos, P., Pach, J. and Spencer, J.: On the mean distance between points of a graph, Congr. Numer.\n64 (1988), 121\u2013124.","journal-title":"Congr. Numer."},{"key":"5114272_CR12","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1002\/net.3230190502","volume":"19","author":"O. Favaron","year":"1989","unstructured":"Favaron, O., Kouider, M. and Maheo, M.: Edge-vulnerability and mean distance, Networks\n19 (1989), 493\u2013504.","journal-title":"Networks"},{"key":"5114272_CR13","first-page":"51","volume":"55","author":"S. Fajtlowich","year":"1986","unstructured":"Fajtlowich, S. and Waller, W. A.: On two conjectures of GRAFFITI, Congr. Numer.\n55 (1986), 51\u201356.","journal-title":"Congr. Numer."},{"key":"5114272_CR14","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M. L. Fredman","year":"1987","unstructured":"Fredman, M. L. and Tarjan, R. E.: Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM\n34 (1987), 596\u2013615.","journal-title":"J. ACM"},{"issue":"6","key":"5114272_CR15","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"R. Floyd","year":"1962","unstructured":"Floyd, R.: Algorithm 97: Shortest path, Comm. ACM\n5(6) (1962), 345.","journal-title":"Comm. ACM"},{"key":"5114272_CR16","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1006\/inco.1997.2620","volume":"134","author":"Z. Galil","year":"1997","unstructured":"Galil, Z. and Margalit, O.: All pairs shortest distances for graphs with small integer length edges, Inform. Comput.\n134 (1997), 103\u2013139.","journal-title":"Inform. Comput."},{"key":"5114272_CR17","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M. C. Golumbic","year":"1980","unstructured":"Golumbic, M. C.: Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980."},{"key":"5114272_CR18","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1002\/net.3230190405","volume":"19","author":"G. R. T. Hendry","year":"1989","unstructured":"Hendry, G. R. T.: On mean distance in certain classes of graphs, Networks\n19 (1989), 451\u2013557.","journal-title":"Networks"},{"key":"5114272_CR19","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1002\/(SICI)1097-0037(199605)27:3<215::AID-NET6>3.0.CO;2-L","volume":"27","author":"P. Mirchandani","year":"1996","unstructured":"Mirchandani, P.: A simple O(n\n2\n) algorithm for all pairs shortest path problem on an interval graph, Networks\n27 (1996), 215\u2013217.","journal-title":"Networks"},{"key":"5114272_CR20","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/BF01789463","volume":"7","author":"B. Mohar","year":"1991","unstructured":"Mohar, B.: Eigenvalues, diameter and mean distance in graphs, Graphs Combin.\n7 (1991), 53\u201364.","journal-title":"Graphs Combin."},{"issue":"2","key":"5114272_CR21","first-page":"103","volume":"3","author":"S. Mondal","year":"2002","unstructured":"Mondal, S., Pal, M. and Pal, T. K.: An optimal algorithm for solving all-pairs shortest paths on trapezoid graphs, Intern. J. Comput. Engg. Sci.\n3(2) (2002), 103\u2013116.","journal-title":"Intern. J. Comput. Engg. Sci."},{"key":"5114272_CR22","unstructured":"Moore, E. F.: The shortest path through a maze, Proc. Internat. Sympos. Switching Theory, 1957, Harvard Univ. Press, 1959, pp. 285\u2013292."},{"key":"5114272_CR23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/58562.59300","volume":"36","author":"J. H. Muller","year":"1989","unstructured":"Muller, J. H. and Spinrad, J.: Incremental modular decomposition, J. ACM\n36 (1989), 1\u201319.","journal-title":"J. ACM"},{"key":"5114272_CR24","first-page":"342","volume":"4","author":"M. Pal","year":"1997","unstructured":"Pal, M. and Bhattacharjee, G. P.: An optimal parallel algorithm for all-pairs shortest paths on unweighted interval graphs, Nordic J. Comput.\n4 (1997), 342\u2013356.","journal-title":"Nordic J. Comput."},{"issue":"3","key":"5114272_CR25","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1142\/S0218126697000127","volume":"7","author":"M. Pal","year":"1997","unstructured":"Pal, M. and Bhattacharjee, G. P.: A data structure on interval graphs and its applications, J. Circuits Systems Comput.\n7(3) (1997), 165\u2013175.","journal-title":"J. Circuits Systems Comput."},{"key":"5114272_CR26","doi-asserted-by":"crossref","first-page":"160","DOI":"10.4153\/CJM-1971-016-5","volume":"23","author":"A. Pnueli","year":"1971","unstructured":"Pnueli, A., Lempel, A. and Even, S.: Transitive orientation of graphs and identification of permutation graphs, Canad. J. Math.\n23 (1971), 160\u2013175.","journal-title":"Canad. J. Math."},{"key":"5114272_CR27","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1002\/net.3230220103","volume":"22","author":"R. Ravi","year":"1992","unstructured":"Ravi, R., Marathe, M. V. and Pandu Rangan, C.: An optimal algorithm to solve the all-pair shortest path problem on interval graphs, Networks\n22 (1992), 21\u201335.","journal-title":"Networks"},{"key":"5114272_CR28","first-page":"745","volume-title":"Proc. 24th ACM STOC","author":"R. Seidel","year":"1992","unstructured":"Seidel, R.: On the all pairs shortest path problem, In: Proc. 24th ACM STOC, ACM Press, New York, 1992, pp. 745\u2013749."},{"key":"5114272_CR29","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1093\/qmath\/40.4.475","volume":"40","author":"I. Tomescu","year":"1989","unstructured":"Tomescu, I. and Melter, R. A.: On distances in chromatic graphs, Quart. J. Math. Oxford (2)\n40 (1989), 475\u2013480.","journal-title":"Quart. J. Math. Oxford (2)"},{"key":"5114272_CR30","first-page":"63","volume":"54","author":"P. Winkler","year":"1986","unstructured":"Winkler, P.: Mean distance and the \u2018four-thirds conjecture\u2019, Congr. Numer.\n54 (1986), 63\u201372.","journal-title":"Congr. Numer."},{"key":"5114272_CR31","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0166-218X(90)90137-2","volume":"27","author":"P. Winkler","year":"1990","unstructured":"Winkler, P.: Mean distance in a tree, Discrete Appl. Math.\n27 (1990), 179\u2013185.","journal-title":"Discrete Appl. Math."}],"container-title":["Journal of Mathematical Modelling and Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1023695531209.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1023695531209\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1023695531209.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,12]],"date-time":"2025-06-12T10:24:34Z","timestamp":1749723874000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1023695531209"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,3]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,3]]}},"alternative-id":["5114272"],"URL":"https:\/\/doi.org\/10.1023\/a:1023695531209","relation":{},"ISSN":["1570-1166","1572-9214"],"issn-type":[{"type":"print","value":"1570-1166"},{"type":"electronic","value":"1572-9214"}],"subject":[],"published":{"date-parts":[[2003,3]]}}}