Name
Abstract | ||
|---|---|---|
The Knödel graphs Wd,n are regular graphs, of even order n and degree d ≤ ⌊log n⌋. They have been introduced by W. Knödel as gossip graphs for d = ⌊log n⌋. A logarithmic algorithm for the minimum path problem in Knödel graphs is an open problem despite the fact that they are bipartite and highly symmetric. In this paper, we describe a logarithmic time two-approximation algorithm for the shortest path in the Knödel graph on 2d vertices with degree d. We also prove that for a subset of the set of vertices, the algorithm gives a minimum length path. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(1), 86–91 2007 |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1002/net.v50:1 | Networks |
Keywords | Field | DocType |
interconnection networks,Knodel graphs,minimum path problem | Graph theory,Discrete mathematics,Combinatorics,Vertex (geometry),Shortest path problem,Bipartite graph,Chordal graph,Ordered graph,Regular graph,Longest path problem,Mathematics | Journal |
Volume | Issue | ISSN |
50 | 1 | 0028-3045 |
Citations | PageRank | References |
10 | 0.76 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hovhannes A. Harutyunyan | 1 | 206 | 28.18 |
| Calin D. Morosan | 2 | 15 | 3.60 |