A VLSI decomposition of the deBruijn graph

DOI10.1145/146585.146620zbMath0809.94038OpenAlexW1971305860MaRDI QIDQ4302796

Oliver Michael Collins, Fabrizio Pollara, Sam Dolinar, Robert J. McEliece

Publication date: 4 April 1995

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/146585.146620

zbMATH Keywords

de Bruijn graphgraph decompositionbuilding blockbinary shift registervery large Viterbi decoder

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15) Modulation and demodulation in information and communication theory (94A14)

Related Items

Partitioning through projections: strong SDP bounds for large graph partition problems, An exact algorithm for graph partitioning, Unnamed Item, On a generalized model of labeled graphs, Some VLSI decompositions of the de Bruijn graph, Approximate Moore graphs are good expanders