Cycle avoidance in 2D/3D bidirectional graphs using shortest-path dynamic programming network
Refereed conference paper presented and published in conference proceedings

CUHK Authors
Author(s) no longer affiliated with CUHK


Times Cited
Altmetrics Information
.

Other information
AbstractAn ordinary-differential-equation (ODE) simulation model has recently been proposed for an N-node dynamic programming (DP) network, which solves the transitive closure and shortest path problems on an architecturally equivalent N-node 2D/3D grid stack. For large-scale randomly generated bidirectional network, where N is large and the inter-grid paths may take either direction, cycles commonly occur leading to a high percentage of nodes with unbound path lengths. The detection of such cycle nodes can be readily found using a shortest-path DP network. In this work we address several issues on the cycle avoidance problem, by first defining the 〈H〉-index and 〈V〉-index and hence its product 〈HV〉 as the two-dimensional turn ability. A regression model was then proposed and obtained empirically to relate the cycle-node ratio, which is the percentage of cycle nodes over N, with 〈HV〉 for several random networks of sizes N = 10x10x2, 10x10x5, 10x10x8. By reducing 〈HV〉 from 0.8 to 0.2, the cycle-node ratio can be reduced from close to 60% to 20% and indicates a significant avoidance of cycle nodes. © 2011 IEEE.
All Author(s) ListLam K.P., Mak T.S.T., Poon C.-S.
Name of Conference2011 IEEE/IFIP 19th International Conference on VLSI and System-on-Chip, VLSI-SoC 2011
Start Date of Conference03/10/2011
End Date of Conference05/10/2011
Place of ConferenceKowloon
Country/Region of ConferenceHong Kong
Detailed descriptionorganized by IEEE,
Year2011
Month12
Day22
Pages354 - 358
ISBN9781457701719
LanguagesEnglish-United Kingdom

Last updated on 2020-08-08 at 00:18