完整後設資料紀錄
DC 欄位語言
dc.contributor.authorHo, TYen_US
dc.contributor.authorSung, TYen_US
dc.contributor.authorHsu, LHen_US
dc.contributor.authorTsai, CHen_US
dc.contributor.authorHwang, JYen_US
dc.date.accessioned2014-12-08T15:48:52Z-
dc.date.available2014-12-08T15:48:52Z-
dc.date.issued1998-08-01en_US
dc.identifier.issn0196-6774en_US
dc.identifier.urihttp://hdl.handle.net/11536/32495-
dc.description.abstractGiven 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.en_US
dc.language.isoen_USen_US
dc.titleThe recognition of double Euler trails in series-parallel networksen_US
dc.typeArticleen_US
dc.identifier.journalJOURNAL OF ALGORITHMSen_US
dc.citation.volume28en_US
dc.citation.issue2en_US
dc.citation.spage216en_US
dc.citation.epage257en_US
dc.contributor.department資訊工程學系zh_TW
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.identifier.wosnumberWOS:000074874500002-
dc.citation.woscount1-
顯示於類別:期刊論文


文件中的檔案:

  1. 000074874500002.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。