Spanners of de Bruijn and Kautz graphs

DOI10.1016/S0020-0190(97)00075-6zbMath1337.68207OpenAlexW1968565259MaRDI QIDQ287077

Carles Padró, Rabah Harbane

Publication date: 26 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(97)00075-6

zbMATH Keywords

interconnection networksbutterfly network\(t\)-spannerde Bruijn networkgeneralized \(p\)-cyclesKautz network

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Minimum spanners of butterfly graphs

Cites Work

• Unnamed Item
• Reconstructing the shape of a tree from observed dissimilarity data
• Spanners of underlying graphs of iterated line digraphs
• Delaunay graphs are almost as good as complete graphs
• Large generalized cycles
• A sparse graph almost as good as the complete graph on points in \(k\) dimensions
• Line Digraph Iterations and the (d, k) Digraph Problem
• Complexity of network synchronization
• Graph spanners
• Spanners in graphs of bounded degree
• An Optimal Synchronizer for the Hypercube
• Spanners of Hypercube-Derived Networks
• Dense bipartite digraphs
• Grid spanners
• Additive graph spanners