On the Edge Importance Using Its Traffic Based on a Distribution Function along Shortest Paths in a Network

Peng CHENG  Shigeru MASUYAMA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E78-A   No.3   pp.440-443
Publication Date: 1995/03/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Graphs, Networks and Matroids
graph theory,  shortest path,  edge importance with respect to traffic,  distribution function,  polynomial time algorithm,  

Full Text: PDF(290.9KB)>>
Buy this Article

We model a road network as a directed graph G(V,E) with a source s and a sink t, where each edge e has a positive length l(e) and each vertex v has a distribution function αv with respect to the traffic entering and leaving v. This paper proposes a polynomial time algorithm for evaluating the importance of each edge e E whicn is defined to be the traffic f(e) passing through e in order to assign the required traffic Fst(0) from s to t along only shortest s-t paths in accordance with the distribution function αv at each vertex v.