标题: 有信心之单容线容错图及一些串并联网路之演算法
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