TY - GEN

T1 - Shortest path length calculation using graph transformations

AU - Mizoguchi, Yoshihiro

PY - 2002

Y1 - 2002

N2 - We consider a graph with labels of edges. A label means the length of an edge. We present a method to compute the length of a shortest path between two vertices using graph transformations. We introduce graph transformation rules which preserve the length ofpaths. Reducing to a simple graph which contains two vertices, we finally calculate the length of a shortest path of those two vertices. There were several algorithms for computing network reliabilities using graph transformations. We use the same framework for applying the graph transformation rules, but our transformation rules do not calculate the network reliabilities but calculate the length of a shortest path.

AB - We consider a graph with labels of edges. A label means the length of an edge. We present a method to compute the length of a shortest path between two vertices using graph transformations. We introduce graph transformation rules which preserve the length ofpaths. Reducing to a simple graph which contains two vertices, we finally calculate the length of a shortest path of those two vertices. There were several algorithms for computing network reliabilities using graph transformations. We use the same framework for applying the graph transformation rules, but our transformation rules do not calculate the network reliabilities but calculate the length of a shortest path.

UR - http://www.scopus.com/inward/record.url?scp=1642414214&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=1642414214&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:1642414214

SN - 0970789017

T3 - Proceedings of the Joint Conference on Information Sciences

SP - 358

EP - 361

BT - Proceedings of the 6th Joint Conference on Information Sciences, JCIS 2002

A2 - Caulfield, J.H.

A2 - Chen, S.H.

A2 - Cheng, H.D.

A2 - Duro, R.

A2 - Caufield, J.H.

A2 - Chen, S.H.

A2 - Cheng, H.D.

A2 - Duro, R.

A2 - Honavar, V.

T2 - Proceedings of the 6th Joint Conference on Information Sciences, JCIS 2002

Y2 - 8 March 2002 through 13 March 2002

ER -