Browsing by Author "Lo, Yuan-Hsun"

Now showing 1 - 11 of 11

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.
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.
Multicolored Isomorphic Spanning Trees in Complete Graphs
(2015-07-01)
Fu, Hung-Lin
;
Lo, Yuan-Hsun
;
應用數學系
;
Department of Applied Mathematics
In this paper, we first prove that if the edges of K-2m are properly colored by 2m - 1 colors in such a way that any two colors induce a 2-factor of which each component is a 4-cycle, then K2m, can be decomposed into m isomorphic multicolored spanning trees. Consequently, we show that there exist three disjoint isomorphic multicolored spanning trees in any properly (2m-1)-edge-colored K-2m for m >= 14.
Multicolored parallelisms of Hamiltonian cycles
(2009-07-28)
Fu, Hung-Lin
;
Lo, Yuan-Hsun
;
應用數學系
;
Department of Applied Mathematics
A subgraph in an edge-colored graph is multicolored if all its edges receive distinct colors. In this paper, we prove that a complete graph on 2m + 1 vertices K(2m+1) can be properly edge-colored with 2m + 1 colors in such a way that the edges of K(2m+1) can be partitioned into m multicolored Hamiltonian cycles. (C) 2009 Published by Elsevier B.V.
New bounds on (2)over-bar-separable codes of length 2
(2015-01-01)
Cheng, Minquan
;
Fu, Hung-Lin
;
Jiang, Jing
;
Lo, Yuan-Hsun
;
Miao, Ying
Let be a code of length over an alphabet of letters. The descendant code of is defined to be the set of words such that for all . is a -separable code if for any two distinct such that , , we always have . The study of separable codes is motivated by questions about multimedia fingerprinting for protecting copyrighted multimedia data. Let be the maximal possible size of such a separable code. In this paper, we provide an improved upper bound for by a graph theoretical approach, and a new lower bound for by deleting suitable points and lines from a projective plane, which coincides with the improved upper bound in some places. This corresponds to the bounds of maximum size of bipartite graphs with girth and a construction of such maximal bipartite graphs.
On the number of rainbow spanning trees in edge-colored complete graphs
(2018-08-01)
Fu, Hung-Lin
;
Lo, Yuan-Hsun
;
Perry, K. E.
;
Rodger, C. A.
;
應用數學系
A spanning tree of a properly edge-colored complete graph, K, is rainbow provided that each of its edges receives a distinct color. In 1996, Brualdi and Hollingsworth conjectured that if K-2m is properly (2m 1)-edge-colored, then the edges of K-2m,, can be partitioned into m rainbow spanning trees except when m = 2. By means of an explicit, constructive approach, in this paper we construct [root 6m+9/3] mutually edge-disjoint rainbow spanning trees for any positive value of m. Not only are the rainbow trees produced, but also some structure of each rainbow spanning tree is determined in the process. This improves upon best constructive result to date in the literature which produces exactly three rainbow trees. (C) 2018 Elsevier B.V. All rights reserved.
Optimal conflict-avoiding codes of odd length and weight three
(2014-08-01)
Fu, Hung-Lin
;
Lo, Yuan-Hsun
;
Shum, Kenneth W.
;
應用數學系
;
Department of Applied Mathematics
A conflict-avoiding code (CAC) of length n and weight k is a collection of k-subsets of such that for any , , where . Let CAC(n, k) denote the class of all CACs of length n and weight k. A CAC with maximum size is called optimal. In this paper, we study the constructions of optimal CACs for the case when n is odd and k = 3.
Partially user-irrepressible sequence sets and conflict-avoiding codes
(2016-03)
Lo, Yuan-Hsun
;
Wong, Wing Shing
;
Fu, Hung-Lin
;
應用數學系
;
Department of Applied Mathematics
In this paper we give a partial shift version of user-irrepressible sequence sets and conflict-avoiding codes. By means of disjoint difference sets, we obtain an infinite number of such user-irrepressible sequence sets whose lengths are shorter than known results in general. Subsequently, the newly defined partially conflict-avoiding codes are discussed.
The Global Packing Number of a Fat-Tree Network
(2017-08-01)
Lo, Yuan-Hsun
;
Zhang, Yijin
;
Chen, Yi
;
Fu, Hung-Lin
;
Wong, Wing Shing
Data centers play an important role in today's Internet development. Research to find scalable architecture and efficient routing algorithms for data center networks has gained popularity. The fat-tree architecture, which is essentially a folded version of a Clos network, has proved to be readily implementable and is scalable. In this paper, we investigate routing on a fat-tree network by deriving its global packing number and by presenting explicit algorithms for the construction of optimal, load-balanced routing solutions. Consider an optical network that employs wavelength division multiplexing in which every user node sets up a connection with every other user node. The global packing number is basically the number of wavelengths required by the network to support such a traffic load, under the restriction that each source-to-destination connection is assigned a wavelength that remains constant in the network. In mathematical terms, consider a bidirectional, simple graph, G and let N subset of V(G) be a set of nodes. A path system P of G with respect to N consists of |N|(|N|-1) directed paths, one path to connect each of the source-destination node pairs in N. The global packing number of a path system P, denoted by Phi(G, N, P), is the minimum integer k to guarantee the existence of a mapping phi : P -> {1, 2, . . . , k}, such that phi(P) not equal phi((P) over cap) if P and (P) over cap have common arc(s). The global packing number of (G, N), denoted by Phi (G, N), is defined to be the minimum Phi (G, N, P) among all possible path systems P. In additional to wavelength division optical networks, this number also carries significance for networks employing time division multiple access. In this paper, we compute by explicit route construction the global packing number of (T-n, N), where T-n denotes the topology of the n-ary fat-tree network, and N is considered to be the set of all edge switches or the set of all supported hosts. We show that the constructed routes are load-balanced and require minimal link capacity at all network links.
The undirected optical indices of complete m-ary trees
(2020-10-15)
Lo, Yuan-Hsun
;
Fu, Hung-Lin
;
Zhang, Yijin
;
Wong, Wing Shing
;
應用數學系
The routing and wavelength assignment problem arises from the investigation of optimal wavelength allocation in an optical network that employs Wavelength Division Multiplexing (WDM). Consider an optical network that is represented by a connected, simple graph G. An all-to-all routing R in G is a set of paths connecting all pairs of vertices of G. The undirected optical index of G is the minimum integer k to guarantee the existence of a mapping phi : R -> {1, 2, ..., k}, such that phi(P) not equal phi(P') if P and P' have common edge(s), over all possible routings R. A natural lower bound of the undirected optical index of G is the (undirected) edge-forwarding index, which is defined to be the minimum of the maximum edge-load over all possible all-to-all routings. In this paper, we first derive the exact value of the optical index of the complete m-ary trees, and then investigate the gap between undirected optical and edge-forwarding indices. (C) 2020 Elsevier B.V. All rights reserved.
Weighted maximum matchings and optimal equi-difference conflict-avoiding codes
(2015-08-01)
Lo, Yuan-Hsun
;
Fu, Hung-Lin
;
Lin, Yi-Hean
;
應用數學系
;
Department of Applied Mathematics
A conflict-avoiding code (CAC) of length and weight is a collection of -subsets of such that for any and , where . Let denote the class of all CACs of length and weight . A CAC is said to be equi-difference if any codeword has the form . A CAC with maximum size is called optimal. In this paper we propose a graphical characterization of an equi-difference CAC, and then provide an infinite number of optimal equi-difference CACs for weight four.