Premium
Clifford algebra method for network expression, computation, and algorithm construction
Author(s) -
Yuan Linwang,
Yu Zhaoyuan,
Luo Wen,
Zhang Jiyi,
Hu Yong
Publication year - 2013
Publication title -
mathematical methods in the applied sciences
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.719
H-Index - 65
eISSN - 1099-1476
pISSN - 0170-4214
DOI - 10.1002/mma.2904
Subject(s) - clifford algebra , geometric algebra , mathematics , algebra over a field , shortest path problem , computation , expression (computer science) , vector space , algorithm , topology (electrical circuits) , computer science , discrete mathematics , pure mathematics , combinatorics , graph , programming language
Clifford algebra is introduced as a theoretical foundation for network topology expression and algorithm construction. Network nodes are coded with basis vectors in a vector spaceR n , and the edges and k ‐walk routes can be expressed by 2‐blades and k ‐blades, respectively, in the Clifford algebra Cl ( n ,0). The topologies among nodes, edges, and routes of networks can be directly calculated, and the network routes can be extended and traversed with oriented join products. The network algorithm construction processes based on Clifford algebra are instantiated by the single source shortest path algorithm. The experimental results on different scale random networks suggest that Clifford algebra is suited for network expression and relation computation. The Clifford algebra‐based shortest path algorithm is vivid and clear in geometric meaning and has great advantage on temporal and spatial complexity. Copyright © 2013 John Wiley & Sons, Ltd.