標題: The recognition of double Euler trails in series-parallel networks
作者: Ho, TY
Sung, TY
Hsu, LH
Tsai, CH
Hwang, JY
資訊工程學系
Department of Computer Science
公開日期: 1-八月-1998
摘要: Given a series-parallel network (network, for short) N,its dual network N' is given by interchanging the series connection and the parallel connection of network N. We usually use a series-parallel graph to represent a network Let G[N] and G[N'] be graph representations of N and N', respectively. A sequence of edges e(1), e(2),...,e(k) is said to form a common trail on (G[N],G[N']) if it is a trail on both G[N] and G[N']. If a common trail covers all of the edges in G[N] and G[N'], it is called a double Euler trail. However, there are many different graph representations for a network. We say that a network N has a double Euler trail (DET) if there is a common Euler trail for some G[N] and some G[N']. Finding a DET in a network is essential for optimizing the layout area of a complementary CMOS functional cell. Maziasz and Hayes (IEEE Trans. Computer-Aided Design 9 (1990), 708-719) gave a linear time algorithm for solving the layout problem in fixed G[N] and G[N'] and an exponential algorithm for finding the optimal cover in a network without fixing graph representations. In this paper, we study properties of subnetworks of a DET network. According to these properties, we propose an algorithm that automatically generates the rules for composition of trail cover classes. On the basis of these rules, a linear time algorithm for recognizing DET networks is presented. Furthermore, we also give a necessary and sufficient condition for the existence of a double Euler circuit in a network. (C) 1998 Academic Press.
URI: http://hdl.handle.net/11536/32495
ISSN: 0196-6774
期刊: JOURNAL OF ALGORITHMS
Volume: 28
Issue: 2
起始頁: 216
結束頁: 257
顯示於類別:期刊論文


文件中的檔案:

  1. 000074874500002.pdf