The (Δ,D) and (Δ,N) problems for New Amsterdam and Manhattan digraphs

2012/10/23 by C. Dalfó, M.A. Fiol, Dalfó, C. +2
Computer Science · Engineering · Mathematics · #05C12 #05C20 #Advanced Optical Network Technologies #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems #cs.DM #math.CO #msc:05C12 #msc:05C20

paper · pdf · doi:10.48550/arxiv.1210.6202

arxiv created 2012/10/23 · openalex publication_date 2012/10/23 · arxiv updated 2012/10/24 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28

Abstract

We give a quasi-complete solution of the (Δ,N) problem for two well-known families of digraphs used as good models for large interconnection networks. In our study we also relate both families, the New Amsterdam and Manhattan digraphs, with the double-step graphs (or circulant graphs with degree two).

Related

• Distance-layer structure of the De Bruijn and Kautz digraphs: analysis and application to deflection routing (with examples and remarks)
• A fixed-parameter algorithm for the minimum Manhattan network problem
• A fixed-parameter algorithm for the minimum Manhattan network problem
• On a composition of digraphs
• On Minimum Generalized Manhattan Connections