Browsing by Author "Fu, Hung-Lin"

Now showing 1 - 20 of 74

(4,5)-CYCLE SYSTEMS OF COMPLETE MULTIPARTITE GRAPHS
(2012-06-01)
Huang, Ming-Hway
;
Fu, Hung-Lin
;
應用數學系
;
Department of Applied Mathematics
In 1981, Alspach conjectured that if 3 <= m(i) <= v, v is odd and v(v - 1)/2 = m(1) +m(2)+ ... +m(t) then the complete graph K-v can be decomposed into t cycles of lengths m(1), m(2), ... , m(t) respectively; if v is even, v(v - 2)/2 = m(1) + m(2) ... + m(t), then the complete graph minus a one-factor K-v - F can be decomposed into t cycles of lengths m(1), m(2),..., Tat respectively. In this paper, we extend the study to the decomposition of the complete equipartite graph K-m(n).For m(i) is an element of {4, 5}, we prove that the trivial necessary conditions are also sufficient.
"(4,5)-CYCLE SYSTEMS OF COMPLETE MULTIPARTITE GRAPHS"
(2012-06-01)
Huang, Ming-Hway
;
Fu, Hung-Lin
;
應用數學系
;
Department of Applied Mathematics
"In 1981, Alspach conjectured that if 3 <= m(i) <= v, v is odd and v(v - 1)/2 = m(1) +m(2)+ ... +m(t) then the complete graph K-v can be decomposed into t cycles of lengths m(1), m(2), ... , m(t) respectively; if v is even, v(v - 2)/2 = m(1) + m(2) ... + m(t), then the complete graph minus a one-factor K-v - F can be decomposed into t cycles of lengths m(1), m(2),..., Tat respectively. In this paper, we extend the study to the decomposition of the complete equipartite graph K-m(n).For m(i) is an element of {4, 5}, we prove that the trivial necessary conditions are also sufficient."
A new construction of 3-separable matrices via an improved decoding of Macula's construction
(2008-11-01)
Fu, Hung-Lin
;
Hwang, F. K.
;
應用數學系
;
Department of Applied Mathematics
Macula proposed a novel construction of pooling designs which can effectively identify positive clones and also proposed a decoding method. However, the probability of all unresolved positive clone is hard to analyze. In this paper we propose an improved decoding method and show that ford d = 3 an exact probability analysis is possible. Further, we derive necessary and Sufficient conditions for a positive clone to be unresolved and gave a modified construction which avoids this necessary condition, thus resulting; in a 3-separable matrix. (c) 2008 Elsevier B.V. All rights reserved.
A note on cyclic m-cycle systems of K-r((m))
(2006-11-01)
Wu, Shung-Liang
;
Fu, Hung-Lin
;
應用數學系
;
Department of Applied Mathematics
It was proved by Buratti and Del Fra that for each pair of odd integers r and m, there exists a cyclic m-cycle system of the balanced complete r-partite graph K-r(m) except for the case when r=m=3. In this note, we study the existence of a cyclic m-cycle system of K-r(m) where r or m is even. Combining the work of Buratti and Del Fra, we prove that cyclic m-cycle systems of K-r(m) exist if and only if (a) K-r(m) is an even graph (b) (r, m) not equal (3, 3) and (c) (r,m) not equivalent to (t , 2) (mod 4) where t is an element of {2,3}.
A note on optimal pebbling of hypercubes
(2013-05-01)
Fu, Hung-Lin
;
Huang, Kuo-Ching
;
Shiue, Chin-Lin
;
應用數學系
;
Department of Applied Mathematics
A pebbling move consists of removing two pebbles from one vertex and then placing one pebble at an adjacent vertex. If a distribution delta of pebbles lets us move at least one pebble to each vertex by applying pebbling moves repeatedly(if necessary), then delta is called a pebbling of G. The optimal pebbling number f'(G) of G is the minimum number of pebbles used in a pebbling of G. In this paper, we improve the known upper bound for the optimal pebbling number of the hypercubes Q (n) . Mainly, we prove for large n, by a probabilistic argument.
A study of total relative Displacements of permutations in paths and cycles
(2008-03-01)
Cheng, Kai-Chung
;
Fu, Hung-Lin
;
Chiang, Nam-Po
;
Tzeng, Chien-Kuo
;
應用數學系
Let G = (V, E) be a connected graph and let phi be a permutation of V. The total relative displacement of the permutation phi in G is delta(phi) (G) = Sigma ({x,y}CV) vertical bar d(x,y) - d(phi(x),phi(y))vertical bar, where d(x, y) means the distance between x and y in G, i.e., the length of a shortest path between x and y. A permutation phi which attains the minimum value of non-zero value of delta(phi)(G) is referred to as a near-automarphism of G and a permutation phi which attains the maximum value of delta(phi)(G) is referred to as a chaotic mapping of G. In this paper, we study the maximum value of delta(phi) (G) among all permutations in paths and cycles.
All graphs with maximum degree three whose complements have 4-cycle decompositions
(2008-07-06)
Fu, Chin-Mei
;
Fu, Hung-Lin
;
Rodger, C. A.
;
Smith, Todd
;
應用數學系
Let g be the set that contains precisely the graphs on n vertices with maximum degree 3 for which there exists a 4-cycle system of their complement in K(n). In this paper g is completely characterized. (C) 2007 Elsevier B.V. All rights reserved.
alpha-labeling number of trees
(2006-12-28)
Shiue, Chin-Lin
;
Fu, Hung-Lin
;
應用數學系
;
Department of Applied Mathematics
In this paper, we prove that the alpha-labeling number of trees T, T-alpha <= [r/2] n where n = vertical bar E(T)vertical bar and r is the radius of T. This improves the known result T-alpha <= e(O(root nlogn)) tremendously and this upper bound is very close to the upper bound T-alpha <= n conjectured by Snevily. Moreover, we prove that a tree with n edges and radius r decomposes K-1 for some t <= (r + 1)n(2) + 1. (c) 2006 Elsevier B.V. All rights reserved.
An improved module-based substitution method for image hiding
(2008)
Chen, Shang-Kuan
;
Lin, Ja-Chen
;
Fu, Hung-Lin
;
應用數學系
;
資訊工程學系
The paper proposes an improved module-based substitution method for image hiding. The method has the following characteristics: (1) The extracted data are lossless. (2) Each k-bit datum is hidden in a pixel of the host image, and the gray-value distortion is not larger than 2(k-1) for most of the pixels. (3) If it is compared with reported lossless Least-Significant-Bits (LSB) or module-based methods, the proposed method is often with better stego-image quality, unless the hidden data are with very strong randomness. (4) The time complexity is also competitive.
An upper bound of the number of tests in pooling designs for the error-tolerant complex model
(2008-06-01)
Chen, Hong-Bin
;
Fu, Hung-Lin
;
Hwang, Frank K.
;
應用數學系
;
Department of Applied Mathematics
Recently pooling designs have been used in screening experiments in molecular biology. In some applications, the property to be screened is defined on subsets of items, instead of on individual items. Such a model is usually referred to as the complex model. In this paper we give an upper bound of the number of tests required in a pooling design for the complex model (with given design parameters) where experimental errors are allowed.
Averting Cascading Failures in Networked Infrastructures: Poset-Constrained Graph Algorithms
(2018-08-01)
Yu, Pei-Duo
;
Tan, Chee Wei
;
Fu, Hung-Lin
;
交大名義發表
;
應用數學系
Cascading failures in critical networked infrastructures that result even from a single source of failure often lead to rapidly widespread outages as witnessed in the 2013 Northeast blackout in Northern America. The ensuing problem of containing future cascading failures by placement of protection or monitoring nodes in the network is complicated by the uncertainty of the failure source and the missing observation of how the cascading might unravel, be it the past cascading failures or the future ones. This paper examines the problem of minimizing the outage when a cascading failure from a single source occurs. A stochastic optimization problem is formulated where a limited number of protection nodes, when placed strategically in the network to mitigate systemic risk, can minimize the expected spread of cascading failure. We propose the vaccine centrality, which is a network centrality based on the partially ordered sets (poset) characteristics of the stochastic program and distributed message-passing, to design efficient approximation algorithms with provable approximation ratio guarantees. In particular, we illustrate how the vaccine centrality and the poset-constrained graph algorithms can be designed to tradeoff between complexity and optimality, as illustrated through a series of numerical experiments. This paper points toward a general framework of network centrality as statistical inference to design rigorous graph analytics for statistical problems in networks.
(C)over-right-arrow(4)-decompositions of D-v\P and D-v boolean OR P where P is a 2-regular subgraph of D-v
(2006-12-01)
Pu, Liqun
;
Fu, Hung-Lin
;
Shen, Hao
;
應用數學系
;
Department of Applied Mathematics
In this paper, we extend the study of C-4-decompositions of the complete graph with 2-regular leaves and paddings to directed versions. Mainly, we prove that if P is a vertex-disjoint union of directed cycles in a complete digraph D-v, then D-v\P and D-v boolean OR Pcan be decomposed into directed 4-cycles, respectively, if and only if v(v-1) - vertical bar E(P)vertical bar = 0 (mod 4) and v(v-1) + vertical bar E(P)vertical bar = 0 (mod 4) where vertical bar E(P)vertical bar denotes the number of directed edges of P, and v >= 8.
(C)over-right-arrow(4)-decompositions of D-vP and D-v boolean OR P where P is a 2-regular subgraph of D-v
(2006-12-01)
Pu, Liqun
;
Fu, Hung-Lin
;
Shen, Hao
;
應用數學系
;
Department of Applied Mathematics
In this paper, we extend the study of C-4-decompositions of the complete graph with 2-regular leaves and paddings to directed versions. Mainly, we prove that if P is a vertex-disjoint union of directed cycles in a complete digraph D-v, then D-vP and D-v boolean OR Pcan be decomposed into directed 4-cycles, respectively, if and only if v(v-1) - vertical bar E(P)vertical bar = 0 (mod 4) and v(v-1) + vertical bar E(P)vertical bar = 0 (mod 4) where vertical bar E(P)vertical bar denotes the number of directed edges of P, and v >= 8.
Codes with the identifiable parent property for multimedia fingerprinting
(2017-04-01)
Cheng, Minquan
;
Fu, Hung-Lin
;
Jiang, Jing
;
Lo, Yuan-Hsun
;
Miao, Ying
Let be a q-ary code of length n and size M, and be the set of ith coordinates of . The descendant code of a sub-code is defined to be . In this paper, we introduce a multimedia analogue of codes with the identifiable parent property (IPP), called multimedia IPP codes or t-MIPPC(n, M, q), so that given the descendant code of any sub-code of a multimedia t-IPP code , one can always identify, as IPP codes do in the generic digital scenario, at least one codeword in . We first derive a general upper bound on the size M of a multimedia t-IPP code, and then investigate multimedia 3-IPP codes in more detail. We characterize a multimedia 3-IPP code of length 2 in terms of a bipartite graph and a generalized packing, respectively. By means of these combinatorial characterizations, we further derive a tight upper bound on the size of a multimedia 3-IPP code of length 2, and construct several infinite families of (asymptotically) optimal multimedia 3-IPP codes of length 2.
Covering graphs with matchings of fixed size
(2010-01-28)
Cariolaro, David
;
Fu, Hung-Lin
;
應用數學系
;
Department of Applied Mathematics
Let m be a positive integer and let G be a graph. We consider the question: can the edge set E(G) of G be expressed as the union of a set M of matchings of G each of which has size exactly m? If this happens, we say that G is [m]-coverable and we call M an [m]-covering of G. It is interesting to consider minimum [m]-coverings, i.e. [m]-coverings containing as few matchings as possible. Such [m]-coverings will be called excessive [m]-factolizations. The number of matchings in an excessive [m]-factorization is a graph parameter which will be called the excessive [m]-index and denoted by chi([m])'. In this paper we begin the study of this new parameter as well as of a number of other related graph parameters. (C) 2008 Elsevier B.V. All rights reserved.
Directed 3-cycle decompositions of complete directed graphs with quadratic leaves
(2009-07-28)
Pu, Liqun
;
Fu, Hung-Lin
;
Shen, Hao
;
應用數學系
;
Department of Applied Mathematics
Let G be a vertex-disjoint union of directed cycles in the complete directed graph D(t), let vertical bar E(G)vertical bar be the number of directed edges of G and suppose G not equal 54 (C) over right arrow (2) boolean OR (C) over right arrow (3) or (C) over right arrow (5) if t = 5, and G not equal (C) over right arrow (3) boolean OR (C) over right arrow (3) if t = 6. It is proved in this paper that for each positive integer t, there exist (C) over right arrow (3)-decompositions for D(t) - G if and only if t(t - 1) -vertical bar E(G)vertical bar equivalent to 0 (mod 3). (C) 2008 Elsevier B.V. All rights reserved.
Edge-colorings of K-m,K-n which Forbid Multicolored Cycles
(2013-03-01)
Fu, Hung-Lin
;
Lo, Yuan-Hsun
;
Pei, Ryo-Yu
;
應用數學系
;
Department of Applied Mathematics
A subgraph in an edge-colored graph is multicolored if all its edges receive distinct colors. In this paper, we study the proper edge-colorings of the complete bipartite graph K-m,K-n which forbid multicolored cycles. Mainly, we prove that (1) for any integer k >= 2, if n >= 5k - 6, then any properly n-edge-colored K-k,K-n contains a multicolored C-2k, and (2) determine the order of the properly edge-colored complete bipartite graphs which forbid multicolored C-6.
Excessive near 1-factorizations
(2009-07-28)
Cariolaro, David
;
Fu, Hung-Lin
;
應用數學系
;
Department of Applied Mathematics
We begin the study of sets of near 1-factors of graphs G of odd order whose union contains all the edges of G and determine, for a few classes of graphs, the mini mum number of near 1-factors in such sets. (C) 2008 Elsevier B.V. All rights reserved.
FEEDBACK VERTEX SET ON PLANAR GRAPHS
(2012-12-01)
Chen, Hong-Bin
;
Fu, Hung-Lin
;
Shih, Chie-Huai
;
應用數學系
;
Department of Applied Mathematics
A feedback vertex set of a graph is a set of vertices whose removal results an acyclic graph. This paper shows that for every planar graph the minimum cardinality of a feedback vertex set is at most three times the maximum number of vertex disjoint cycles in the graph.
Graph Algorithms for Preventing Cascading Failures in Networks
(2018-01-01)
Yu, Pei Duo
;
Tan, Chee Wei
;
Fu, Hung-Lin
;
交大名義發表
;
National Chiao Tung University
Cascading failures in critical networked infrastructures that result even from a single source of failure often lead to rapidly widespread outages as witnessed in the 2013 Northeast blackout in northern America. This paper examines the problem of minimizing the outage when a cascading failure from a single source occurs. An optimization problem is formulated where a limited number of protection nodes, when placed strategically in the network to mitigate systemic risk, can minimize the spread of cascading failure. Computationally fast distributed message-passing algorithms are developed to solve this problem. Global convergence and the optimality of the algorithm are proved using graph theoretic analysis. In particular, we illustrate how the poset-constrained graph algorithms can be designed to address the trade-off between complexity and optimality.