Article

Optimal Routing Algorithms for Generalized de Bruijn Digraphs

Authors:

Guoping Liu,

Kyungsook Y. LeeAuthors Info & Claims

ICPP '93: Proceedings of the 1993 International Conference on Parallel Processing - Volume 03

Pages 167 - 174

https://doi.org/10.1109/ICPP.1993.130

Published: 16 August 1993 Publication History

Publisher Site

Abstract

Generalized de Bruijn digraph, G_{B}(d,n), was proposed independently by Imase and Itoh, and Reddy, Pradhan and Kuhl to include any number of nodes. Du and Hwang showed that G_{B}(d, n) essentially retains all the nice properties of de Bruijn digraphs, and presented a \left\lceil {\log _d n} \right\rceil -step routing algorithm, where d is the indegree and outdegree, and n is the number of nodes in the graph.

Cited By

View all

Cılasun HResch SChowdhury ZOlson EZabihi MZhao ZPeterson TParhi KWang JSapatnekar SKarpuzcu U(2021)Spiking Neural Networks in Spintronic Computational RAMACM Transactions on Architecture and Code Optimization10.1145/347596318:4(1-21)Online publication date: 29-Sep-2021
https://dl.acm.org/doi/10.1145/3475963
Li KWang S(2017)Design Methodology of Fault-Tolerant Custom 3D Network-on-ChipACM Transactions on Design Automation of Electronic Systems10.1145/305474522:4(1-20)Online publication date: 20-May-2017
https://dl.acm.org/doi/10.1145/3054745
Condo CMartina MRuo Roch MMasera G(2015)Exploiting generalized de-Bruijn/Kautz topologies for flexible iterative channel code decoder architecturesIntegration, the VLSI Journal10.1016/j.vlsi.2014.11.00350:C(139-146)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1016/j.vlsi.2014.11.003
Show More Cited By

Index Terms

Optimal Routing Algorithms for Generalized de Bruijn Digraphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

On efficient absorbant conjecture in generalized De Bruijn digraphs

An absorbant of a digraph D is a set <inline-formula><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" href="gcom_a_1154949_ilm0001.gif"/></inline-formula> such that, for every <inline-formula><inline-graphic xmlns:xlink="http://www.w3.org/1999/...
On semicomplete multipartite digraphs whose king sets are semicomplete digraphs

Reid [Every vertex a king, Discrete Math. 38 (1982) 93-98] showed that a non-trivial tournament H is contained in a tournament whose 2-kings are exactly the vertices of H if and only if H contains no transmitter. Let T be a semicomplete multipartite ...
Absorbant of generalized de Bruijn digraphs

The generalized de Bruijn digraph G"B(n,d) has good properties as an interconnection network topology. The resource location problem in an interconnection network is one of the facility location problems. Finding absorbants of a digraph corresponds to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICPP '93: Proceedings of the 1993 International Conference on Parallel Processing - Volume 03

August 1993

305 pages

ISBN:0849389836

Publisher

IEEE Computer Society

United States

Publication History

Published: 16 August 1993

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Cılasun HResch SChowdhury ZOlson EZabihi MZhao ZPeterson TParhi KWang JSapatnekar SKarpuzcu U(2021)Spiking Neural Networks in Spintronic Computational RAMACM Transactions on Architecture and Code Optimization10.1145/347596318:4(1-21)Online publication date: 29-Sep-2021
https://dl.acm.org/doi/10.1145/3475963
Li KWang S(2017)Design Methodology of Fault-Tolerant Custom 3D Network-on-ChipACM Transactions on Design Automation of Electronic Systems10.1145/305474522:4(1-20)Online publication date: 20-May-2017
https://dl.acm.org/doi/10.1145/3054745
Condo CMartina MRuo Roch MMasera G(2015)Exploiting generalized de-Bruijn/Kautz topologies for flexible iterative channel code decoder architecturesIntegration, the VLSI Journal10.1016/j.vlsi.2014.11.00350:C(139-146)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1016/j.vlsi.2014.11.003
Sabbaghi-Nadooshan RPatooghy A(2015)Analytical performance modeling of de Bruijn inspired mesh-based network-on-chipsMicroprocessors & Microsystems10.1016/j.micpro.2014.12.00239:1(27-36)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1016/j.micpro.2014.12.002
Liu GLee KJordan H(2000)n-Dimensional Processor Arrays with Optical dBusesThe Journal of Supercomputing10.1023/A:100815682484416:3(149-163)Online publication date: 1-Jul-2000
https://dl.acm.org/doi/10.1023/A%3A1008156824844

Abstract

Cited By

Index Terms

Recommendations

On efficient absorbant conjecture in generalized De Bruijn digraphs

On semicomplete multipartite digraphs whose king sets are semicomplete digraphs

Absorbant of generalized de Bruijn digraphs

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations