An optimal algorithm to solve the all-pairs shortest paths problem on permutation graphs

DOI10.1023/A:1023695531209zbMath1056.68169OpenAlexW1487407889MaRDI QIDQ1398021

Madhumangal Pal, Sukumar Mondal, Tapan Kumar Pal

Publication date: 6 August 2003

Published in: JMMA. Journal of Mathematical Modelling and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1023695531209

zbMATH Keywords

analysis of algorithmsdesign of algorithmsshortest pathspermutation graphsaverage distance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10)

Related Items (8)

Algorithms for the rainbow vertex coloring problem on graph classes ⋮ \(L(0,1)\)-labelling of permutation graphs ⋮ Computation of diameter, radius and center of permutation graphs ⋮ Succinct permutation graphs ⋮ An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs ⋮ Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes ⋮ An efficient algorithm to find next-to-shortest path on permutation graphs ⋮ An efficient PRAM algorithm for maximum-weight independent set on permutation graphs

This page was built for publication: An optimal algorithm to solve the all-pairs shortest paths problem on permutation graphs