Title :
On VLSI decompositions for d-ary de Bruijn graphs (extended abstract)
Author :
Yamada, Toshinori ; Kawakita, Hiroyuki ; Nishiyama, Tadashi ; Ueno, Shuichi
Author_Institution :
Dept. of Inf. & Comput. Sci., Saitama Univ., Japan
Abstract :
A VLSI decomposition of a graph G is a collection of isomorphic vertex-disjoint subgraphs (called building blocks) of G which together span G. The efficiency of a VLSI decomposition is the fraction of the edges of G which are present in the subgraphs. The paper gives a necessary condition and a sufficient condition for a graph to be a building block for d-ary de Bruijn graphs. We also show building blocks for d-ary de Bruijn graphs with asymptotically optimal efficiency. Furthermore, we list the most efficient universal d-ary de Bruijn building blocks we know of.
Keywords :
VLSI; circuit theory; graph theory; VLSI decomposition; building blocks; d-ary de Bruijn graphs; isomorphic vertex-disjoint subgraphs; necessary condition; sufficient condition; Coupling circuits; Decoding; Sufficient conditions; Terminology; Very large scale integration; Viterbi algorithm;
Conference_Titel :
Circuits and Systems, 2005. ISCAS 2005. IEEE International Symposium on
Print_ISBN :
0-7803-8834-8
DOI :
10.1109/ISCAS.2005.1464848