Name
Abstract | ||
|---|---|---|
We formally define the $n$-dimensional Manhattan street network $M_n$—a special case of an $n$-regular digraph—and we study some of its structural properties. In particular, we show that $M_n$ is a Cayley digraph, which can be seen as a subgroup of the $n$-dimensional version of the wallpaper group $pgg$. These results induce a useful new representation of $M_n$, which can be applied to design a local (shortest-path) routing algorithm and to study some other metric properties, such as the diameter. We also show that the $n$-dimensional Manhattan street networks are Hamiltonian and, in the standard case (that is, in dimension two), we give sufficient conditions for a $2$-dimensional Manhattan street network to be decomposable into two arc-disjoint Hamiltonian cycles. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1137/07068446X | SIAM J. Discrete Math. |
Keywords | Field | DocType |
sufficient condition,standard case,dimensional version,special case,multidimensional manhattan street networks,dimensional manhattan street network,arc-disjoint hamiltonian cycle,cayley digraph,metric property,regular digraph,structural property,hamiltonian cycle,diameter | Discrete mathematics,Combinatorics,Shortest path problem,Hamiltonian (quantum mechanics),Street network,Hamiltonian path,Directed graph,Mathematics,Digraph,Special case,Routing algorithm | Journal |
Volume | Issue | ISSN |
22 | 4 | 0895-4801 |
Citations | PageRank | References |
1 | 0.39 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| F. Comellas | 1 | 254 | 24.10 |
| Cristina Dalfó | 2 | 46 | 9.47 |
| M. A. Fiol | 3 | 816 | 87.28 |