Browsing by Author "Lu, Hui-Chuan"

Now showing 1 - 7 of 7

MINIMIZING SONET ADMs IN UNIDIRECTIONAL WDM RINGS WITH GROOMING RATIO SEVEN
(2008)
Colbourn, Charles J.
;
Fu, Hung-Lin
;
Ge, Gennian
;
Ling, Alan C. H.
;
Lu, Hui-Chuan
In order to reduce the number of add-drop multiplexers (ADMs) in SONET/WDM networks using wavelength add-drop multiplexing, certain graph decompositions can be used to form a "grooming" that specifies the assignment of traffic to wavelengths. When traffic among nodes is all-to-all and uniform, the drop cost of such a decomposition is the sum, over all graphs in the decomposition, of the number of vertices of nonzero degree in the graph. The number of ADMs required is this drop cost. The existence of such decompositions with minimum cost, when every pair of sites employs no more than 1/7 of the wavelength capacity, is determined within an additive constant. Indeed when the number n of sites satisfies n equivalent to 1 (mod 3) and n not equal 19, the determination is exact; when n equivalent to 0 (mod 3), n not equivalent to 18 (mod 24), and n is large enough, the determination is also exact; and when n equivalent to 2 ( mod 3) and n is large enough, the gap between the cost of the best construction and the cost of the lower bound is independent of n and does not exceed 4.
New bounds on the average information rate of secret-sharing schemes for graph-based weighted threshold access structures
(2013-08-10)
Lu, Hui-Chuan
;
Fu, Hung-Lin
;
應用數學系
;
Department of Applied Mathematics
A secret-sharing scheme is a protocol by which a dealer distributes shares of a secret key among a set of n participants in such a way that only qualified subsets of participants can reconstruct the secret key from the shares they received, while unqualified subsets have no information about the secret key. The collection of all qualified subsets is called the access structure of this scheme. The information rate (resp. average information rate) of a secret-sharing scheme is the ratio between the size of the secret key and the maximum size (resp. average size) of the shares. In a weighted threshold scheme, each participant has his or her own weight. A subset is qualified if and only if the sum of the weights of participants in the subset is not less than the given threshold. Morillo et al. [19] considered the schemes for weighted threshold access structure that can be represented by graphs called k-weighted graphs. They characterized this kind of access structures and derived a result on the information rate. In this paper, we deal with the average information rate of the secret-sharing schemes for these structures. Two sophisticated constructions are presented, each of which has its own advantages and both of them perform very well when n/k is large. (C) 2013 Elsevier Inc. All rights reserved.
New results on harmonious trees
(2007-11-01)
Lu, Hui-Chuan
;
Fu, Hung-Lin
;
應用數學系
;
Department of Applied Mathematics
In this paper, we mainly obtain a couple of new constructions for constructing harmonious trees from smaller sequential trees. Subsequently, we obtain two new classes of harmonious trees called palm tree and firework. As a consequence of adjoining an even number of paths, we disprove an earlier claim by Cahit [1] in investigating harmonious p-stars.
The exact values of the optimal average information ratio of perfect secret-sharing schemes for tree-based access structures
(2014-10-01)
Lu, Hui-Chuan
;
Fu, Hung-Lin
;
應用數學系
;
Department of Applied Mathematics
A perfect secret-sharing scheme is a method of distributing a secret among a set of participants such that only qualified subsets of participants can recover the secret and the joint shares of the participants in any unqualified subset is statistically independent of the secret. The set of all qualified subsets is called the access structure of the scheme. In a graph-based access structure, each vertex of a graph represents a participant and each edge of represents a minimal qualified subset. The information ratio of a perfect secret-sharing scheme is defined as the ratio between the maximum length of the share given to a participant and the length of the secret. The average information ratio is the ratio between the average length of the shares given to the participants and the length of the secret. The infimum of the (average) information ratios of all possible perfect secret-sharing schemes realizing a given access structure is called the (average) information ratio of the access structure. Very few exact values of the (average) information ratio of infinite families of access structures are known. Csirmaz and Tardos have found the information ratio of all trees. Based on their method, we develop our approach to determining the exact values of the average information ratio of access structures based on trees.
The exact values of the optimal average information ratio of perfect secret-sharing schemes for tree-based access structures
(2014-10-01)
Lu, Hui-Chuan
;
Fu, Hung-Lin
;
應用數學系
;
Department of Applied Mathematics
A perfect secret-sharing scheme is a method of distributing a secret among a set of participants such that only qualified subsets of participants can recover the secret and the joint shares of the participants in any unqualified subset is statistically independent of the secret. The set of all qualified subsets is called the access structure of the scheme. In a graph-based access structure, each vertex of a graph represents a participant and each edge of represents a minimal qualified subset. The information ratio of a perfect secret-sharing scheme is defined as the ratio between the maximum length of the share given to a participant and the length of the secret. The average information ratio is the ratio between the average length of the shares given to the participants and the length of the secret. The infimum of the (average) information ratios of all possible perfect secret-sharing schemes realizing a given access structure is called the (average) information ratio of the access structure. Very few exact values of the (average) information ratio of infinite families of access structures are known. Csirmaz and Tardos have found the information ratio of all trees. Based on their method, we develop our approach to determining the exact values of the average information ratio of access structures based on trees.
The optimal average information ratio of secret-sharing schemes for the access structures based on unicycle graphs and bipartite graphs
(2017-12-31)
Lu, Hui-Chuan
;
Fu, Hung-Lin
;
應用數學系
;
Department of Applied Mathematics
In this paper, we derive bounds on the optimal average information ratio of the access structures based on general graphs and investigate the value of the ratio for unicycle graphs and some bipartite graphs. We determine the exact values of this ratio for some infinite classes of bipartite graphs and unicycle graphs. This extends previous results. We also provide good bounds on the optimal average information ratio for all unicycle graphs. (C) 2017 Elsevier B.V. All rights reserved.
Trees Which Admit No alpha-labelings
(2012-01-01)
Shiue, Chin-Lin
;
Lu, Hui-Chuan
;
應用數學系
;
Department of Applied Mathematics
In this paper, we study the existence of alpha-labelings for trees by means of particular (0, 1)-matrices called alpha-labeling matrices. It is shown that each cornet S(k,q) admits no alpha-labelings whenever k > 4(q - 1) and q >= 2. We also give the sufficient conditions for the nonexistence of alpha-labelings for trees of diameter at most six. This extends a result of Rosa's. As a consequence, we prove that S(k,3) has an alpha-labeling if and only if k <= 4.