DocumentCode :
3543068
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
fYear :
2005
fDate :
23-26 May 2005
Firstpage :
1358
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Circuits and Systems, 2005. ISCAS 2005. IEEE International Symposium on
Print_ISBN :
0-7803-8834-8
Type :
conf
DOI :
10.1109/ISCAS.2005.1464848
Filename :
1464848
Link To Document :
بازگشت