A simple  O ( n  2 ) algorithm for the all‐pairs shortest path problem on an interval graph | Zendy

Mirchandani Prakash | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

A simple O ( n 2 ) algorithm for the all‐pairs shortest path problem on an interval graph

Author(s) -

Mirchandani Prakash

Publication year - 1996

Publication title -

networks

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.977

H-Index - 64

eISSN - 1097-0037

pISSN - 0028-3045

DOI - 10.1002/(sici)1097-0037(199605)27:3<215::aid-net6>3.0.co;2-l

Subject(s) - shortest path problem , graph , widest path problem , yen's algorithm , combinatorics , computer science , path graph , algorithm , shortest path faster algorithm , distance , floyd–warshall algorithm , mathematics , path (computing) , interval (graph theory) , dijkstra's algorithm , line graph , graph power , programming language

Let G denote an interval graph with n vertices and unit weight edges. In this paper, we present a simple O ( n 2 ) algorithm for solving the all‐pairs shortest path problem on graph G. A recent algorithm for this problem has the same time‐complexity but is fairly complicated to describe. However, our algorithm is concise to state, intuitive to understand, and easy to implement. © 1996 John Wiley & Sons, Inc.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research