Browsing by Author "Liaw, SC"

Now showing 1 - 8 of 8

A simple and direct derivation for the number of noncrossing partitions
(1998-06-01)
Liaw, SC
;
Yeh, HG
;
Hwang, FK
;
Chang, GJ
;
應用數學系
Kreweras considered the problem of counting noncrossing partitions of the set {1, 2, ..., n}, whose elements are arranged into a cycle in its natural order, into p parts of given sizes n(1), n(2), ..., n(p) (but not specifying which part gets which size). He gave a beautiful and surprising result whose proof resorts to a recurrence relation. In this paper we give a direct, entirely bijective, proof starting from the same initial idea as Kreweras' proof.
Generalized diameters and Rabin numbers of networks
(1999)
Liaw, SC
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
Reliability and efficiency are important criteria in the design of interconnection networks. Recently, the w-wide diameter d(w) (G), the (w - 1)-fault diameter D-w (G), and the w-Rabin number r(w)(G) have been used to measure network reliability and efficiency In this paper, we study d(w)(G), D-w (G) and r(w)(G) using the strong w-Rabin number r(w)(*)(G) for 1 less than or equal to w less than or equal to k(G) and G is a circulant network G(d(n); (1, d,..., d(n-1))), a d-ary cube network C(d, n), a generalized hypercube GH(m(n-1),...,m(0)), a folded hypercube FH(n) or a WK-recursive network WK(d, t).
Integral sum numbers of graphs
(2000-01-01)
Liaw, SC
;
Kuo, D
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
The sum graph of a set S of positive integers is the graph G(+)(S) having S as its vertex set, with two distinct vertices adjacent whenever their sum is in S. If S is allowed to be a subset of all integers, a graph so obtained is called an integral sum graph. The integral sum number of a given graph G is the smallest number of isolated vertices which when added to G result in an integral sum graph. In this paper, we find the integral sum numbers of caterpillars, cycles, wheels, and complete bipartite graphs.
On nonblocking multicast three-stage Clos networks
(2000-08-01)
Hwang, FK
;
Liaw, SC
;
應用數學系
;
Department of Applied Mathematics
We give necessary and sufficient conditions for strictly nonblocking three-stage Clos networks with two types of multicast traffic, Then, we extend the results to other models where the routing is under certain restrictions. Finally, we compare our results with existing literature to mark the differences and similarities.
Rabin numbers of Butterfly networks
(1999-02-06)
Liaw, SC
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
Reliability and efficiency are important criteria in the design of interconnection networks. Recently, the w-wide diameter d(w)(G), the (w - 1)-fault diameter D-w(G), and the w-Rabin number r(w)(G) have been used to measure network reliability and efficiency. In this paper, we study these parameters for an important class of parallel networks - Butterfly networks. The main result of this paper is to determine the Rabin number of Butterfly networks. (C) 1999 Elsevier Science B.V. All rights reserved.
Strictly nonblocking three-stage clos networks with some rearrangeable multicast capability
(2003-11-01)
Hwang, FK
;
Liaw, SC
;
Tong, LD
;
應用數學系
;
Department of Applied Mathematics
Hwang and Lin introduced a new nonblocking requirement for 2-cast traffic which imposes different requirements on different types of coexisting calls. The requirement is strictly nonblocking for point-to-point calls among the 2-cast traffic, and is rearrangeable for genuine 2-cast calls. We generalize the 2-cast calls to multicast calls and give a sufficient condition for such networks when the number of multicast calls is upper bounded.
The L(2,1)-labeling problem on ditrees
(2003-01-01)
Chang, GJ
;
Liaw, SC
;
應用數學系
;
Department of Applied Mathematics
An L(2, 1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that f(x)-f(y) greater than or equal to 2 if d(G)(x,y) =1 and f(x)-f(y) greater than or equal to 1 if d(G)(x,y) = 2. The L(2, 1)-labeling problem is to find the smallest number lambda(G) such that there exists a L(2, 1)-labeling function with no label greater than lambda(G). Motivated by the channel assignment problem introduced by Hale, the L(2, 1)-labeling problem has been extensively studied in the past decade. In this paper, we study this concept for digraphs. In particular, results on ditrees are given.
Wide diameters of butterfly networks
(1999-03-01)
Liaw, SC
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
Reliability and efficiency are important criteria in the design of interconnection networks. Recently, the w-wide diameter d(w)(G), the (w - I)-fault diameter D-w(G), and the w-Rabin number r(w)(G) have been used to measure network reliability and efficiency. In this paper, we study wide diameters for an important class of parallel networks-butterfly networks. The main result of this paper is to determine their wide diameters.