A Caltech Library Service

VLSI decompositions for deBruijn graphs

Dolinar, Sam and Ko, Tsz-Mei and McEliece, Robert J. (1992) VLSI decompositions for deBruijn graphs. In: Proceedings 1992 IEEE International Symposium on Circuits and Systems. IEEE , Piscataway, NJ, pp. 1855-1858. ISBN 0-7803-0593-0.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


A C-chip VLSI decomposition of a graph G is a collection of C isomorphic disjoint subgraphs of G (the building blocks), which together contain all of G's vertices. The efficiency of such a decomposition is defined to be the fraction of edges of G that are in the building block. Motivated by the need to construct large Viterbi decoders, the authors study VLSI decompositions of deBruijn graphs. They obtain some strong necessary conditions for a graph to be a building block for a deBruijn graph, and some slightly more restrictive sufficient conditions which allow the construction of some efficient building blocks for deBruijn graphs.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 1992 IEEE. The research described in this paper was partially carried out at the Jet Propulsion Laboratory, California Institute of Technology, under a contract with the National Aeronautics and Space Administration. Tsz-Mei Ko's contribution was also supported by National Security Agency Grant No. MDA904-90-H-1007. Robert McEliece's contribution was also supported by AFOSR grant 91-0037 and a grant from Pacific Bell.
Funding AgencyGrant Number
National Security AgencyMDA904-90-H-1007
Air Force Office of Scientific Research (AFOSR)91-0037
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number4407484
Record Number:CaltechAUTHORS:20120328-130309049
Persistent URL:
Official Citation:Dolinar, S.; Ko, T.-M.; McEliece, R.; , "VLSI decompositions for deBruijn graphs," Circuits and Systems, 1992. ISCAS '92. Proceedings., 1992 IEEE International Symposium on , vol.4, no., pp.1855-1858 vol.4, 3-6 May 1992 doi: 10.1109/ISCAS.1992.230451 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:29881
Deposited By: Tony Diaz
Deposited On:17 Apr 2012 21:31
Last Modified:09 Nov 2021 19:31

Repository Staff Only: item control page