标题: | 有信心之单容线容错图及一些串并联网路之演算法 Faithful 1-Edge Fault Tolerant Graphs and Some Graph Algorithms on Series-Parallel Networks |
作者: | 汪世义 Wang, Shih-Yih 徐力行 Hsu, Lih-Hsing 资讯科学与工程研究所 |
关键字: | 单线容错图;串并联网路;1-Edge Fault Tolerant Graph;Series-Parallel Networks |
公开日期: | 1997 |
摘要: | 在本篇论文中,要讨论三个问题 (一)有信心的单线容错图 (二)串 并联网路上一般的演算法及 (三)串并联网路中之平行演算法的树收缩. 针对有信心的单线容错图.我们在第二章介绍其优越的特性.依此方法可建 立 n维环状的最佳单线容错图.电路的模式可用串并联网路表示之.在第三 章我们发展出一个计算串并联网路中最大配对数与最小配对数与最小控制 数的演算法,此演算法只需要线性的时间;针对串并联网路中之平行演算的 树收缩,我们建立一个平行演算法,此演算法在串并联网路中可平行计算一 些非对称函数. Three research topics are discussed in this study. These three issuesare the faithful edge fault tolerant graphs, algorithms for series-parallelnetworks and associated parallel algorithms. A graph $G^*$ is defined as$1$-edge fault tolerant with respect to a graph $G$, denotedby $1$-EFT($G$), if any graph obtained by removing an edge from $G^*$contains $G$. And the $1$-EFT($G$) graph isoptimal if it contains the minimum numberof edges among all $1$-EFT($G$) graphs. Let $G_i^*$ be $1$-EFT($G_i$) for$i=1, 2$. Then it can be easily verified that the cartesian product graph $G_1^*\times G_2^*$ is $1$-edge fault tolerant with respect to the cartesian productgraph $G_1 \times G_2$. However, $G_1^* \times G_2^*$ may contain too manyedges; hence it may not be optimal for many cases. In this study, thisproblem is overcome by introducingthe concept of faithful graph with respect to a given graph, which is proved to be 1-edge fault tolerant. Based on this concept,the construction method of $k$-EFT graphs for the cartesianproduct of several graphs is presented. Applying thisconstruction scheme, the optimal $1$-edge fault tolerant graphswith respect to $n$-dimensional tori $C(m_1, m_2, \ldots , m_n)$, where$m_i \geq 4$ are even integers for all $1 \le i \le n$, can be obtainedefficiently. Series-parallel networks have a lot of application.They are often used as models for electric circuits. In this study,series-parallel graphs are used to represent the series-parallel networks.Since there are many different graph representations for a series- parallelnetwork, our interest is focused on studying the maximum and minimummatching in different graph representations of a single network. Thelinear time algorithms are presented to compute the maximum and theminimum matching numbers and the minimum domination number for anyseries-parallel network $N$. It has been proved that everyseries-parallel network $N$ corresponds to a parse-tree $T(N)$. In manyapplications, there is a need to evaluate a parameter $F(N)$ for aseries-parallel network $N$. And this evaluation was implemented byevaluate $F( N)$ sequentially using dynamic programming techniques on$T(N)$. If the function $F$ is symmetric, the tree contraction techniquecould be used to evaluate $F(N)$ in parallel. However, many functionsdefined on series-parallel networks are non- symmetric. In this study,the idea of tree contraction to compute non-symmetric functions $F$ inparallel on the series-parallel networks is applied. Future work and theconclusion are also presented. |
URI: | http://140.113.39.130/cdrfb3/record/nctu/#NT860394008 http://hdl.handle.net/11536/62833 |
显示于类别: | Thesis |