On Finding a Shortest Path in Circulant Graphs with Two Jumps

摘要：

In this paper we present algorithms for finding a shortest path between two vertices of any weighted undirected and directed circulant graph with two jumps. Our shortest path algorithm only requires O (log N) arithmetic steps and the total bit complexity is O(log3 N), where N is the number of the graphs vertices. This method has been derived from some Closest Vector Problems (CVP) of lattices in dimension two and with l1-norm.

作者: Domingo Gomez Jaime Gutierrez Alvar Ibeas Carmen Martinez Ramon Beivide

作者单位: Faculty of Sciences, University of Cantabria Santander E-39071, Spain

会议类型: 国际会议

会议名称: The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)

会议地点: 昆明

会议语种:英文

页码: 777-786

在线出版日期: 2005-08-01（万方平台首次上网日期，不代表论文的发表时间）