Browsing by Author "HSU, LH"

Now showing 1 - 20 of 21

A CLASS OF ADDITIVE MULTIPLICATIVE GRAPH FUNCTIONS
(1987-05-01)
HSU, LH
;
CHEN, C
;
JEAN, EY
;
交大名義發表
;
應用數學系
A LINEAR-TIME ALGORITHM TO RECOGNIZE THE DOUBLE EULER TRAIL FOR SERIES-PARALLEL NETWORKS
(1991)
HSU, LH
;
HWANG, JY
;
HO, TY
;
TSAI, CH
;
資訊工程學系
A NOTE ON THE MINIMUM CUT COVER OF GRAPHS
(1994-05-01)
HO, TY
;
HSU, LH
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
Loulou formulates the problem of minimizing the test time for printed circuit boards into that of minimizing the cardinality of cut cover for graphs. This note shows that the minimum cardinality of cut cover for a graph G is inverted left perpendicular log2 chi(G) inverted right perpendicular. This result enables us to conclude that the problem of determining the minimum cardinality of cut cover is NP-hard. It is also known that every planar graph is 4-colorable. Thus, if the layouts of printed circuit board form a planar graph, the minimum time needed to test the circuits is at most 2.
AN OPTIMAL ALGORITHM FOR FINDING THE MOST VITAL EDGE WITH RESPECT TO SKT RELIABILITY IN BSP DIGRAPHS
(1995-07-01)
WANG, PF
;
LEU, SC
;
HSU, LH
;
資訊工程學系
;
Department of Computer Science
The SKT reliability is the probability that a source can send communication to a specified set of terminals K in V in a probabilistic digraph D = (V, E). ''The most vital edge'' is the edge whose deletion yields the largest decrease in the SKT reliability. A digraph is a basically-series-parallel(BSP) directed graph if its underlying undirected graph is series-parallel. In this paper, we propose a tree-like structure and present an optimal algorithm with linear time complexity for finding the most vital edge with respect to SKT reliability in BSP digraphs.
DATA STRUCTURE FOR GRAPH REPRESENTATIONS OF A NETWORK HAVING DOUBLE EULER TRAILS
(1992)
SUNG, TY
;
HSU, LH
;
HWANG, JY
;
資訊工程學系
;
Department of Computer Science
A network that has a double Euler trail (DET) is called a DET network. A DET network may realize various DETs in different graph representations. Furthermore, a pair of specific graph representations for a DET network may realize different DETs. Based on above considerations, we introduce a data structure PQQ'-tree to keep DETs in all graph representations for any DET network.
DEPENDENCE OF TREE COPY FUNCTIONS
(1985)
HSU, LH
;
交大名義發表
;
應用數學系
;
National Chiao Tung University
;
Department of Applied Mathematics
ELEMENT PERTURBATION PROBLEMS OF OPTIMUM SPANNING-TREES WITH 2-PARAMETER OBJECTIVES
(1994)
CHANG, YC
;
HSU, LH
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
Let G = (V, E) be a graph. We associate with each edge ei E E an ordered pair of rational numbers (ni, bi). Let the weight of a spanning tree T, w(T), be defined as (Sigma(ei is an element of T) a(i))(2) + (Sigma(ei is an element of T) b(i))(2). A spanning tree T in G is called an optimum spanning tree if w(T) greater than or equal to w(T') for all spanning trees T' in G. The problem of finding the optimum spanning tree of the two-parameter objective is called MST2P. Hassin and Tamir have proposed an O(q(6)) algorithm for solving: MST2P, where q = E. Let f(G) denote the weight of the optimum spanning tree of G. The element perturbation problem of MST2P is to compute f(G - e(k)) for all e(k) is an element of E. In this paper, we present an O(q(6)) algorithm to solve the element perturbation problem of MST2P. Our algorithm can also be applied to the EPP of minimal cost/reliability ratio spanning tree problem in communication network design.
ELEMENT PERTURBATION PROBLEMS OF OPTIMUM SPANNING-TREES WITH 2-PARAMETER OBJECTIVES
(1995-01-13)
CHANG, YC
;
HSU, LH
;
資訊工程學系
;
Department of Computer Science
Let G = (V,E) be a graph. We associate with each edge e(i) is an element of E an ordered pair of rational numbers (a(i), b(i)). Let the weight of a spanning tree T, w(T), be defined as Sigma(ei is an element of T) a(i) + Pi(ei is an element of T) b(i). A spanning tree T in G is called a w-optimum spanning tree if w(T) greater than or equal to w(T') for all spanning trees T' in G. The function w is one instance in a class of two-parameter objectives. Hassin and Tamir proposed a unified approach for solving the class of two-parameter objective optimum spanning tree problems. Let s be an objective in the class and F-s(G) denote the weight of the s-optimum spanning tree of G. The element perturbation problem of the s-optimum spanning tree is to compute F-s(G - e(k)) for all e(k) is an element of E. With Hassin and Tamir's approach, let t(s)(p, q) be the complexity of computing the s-optimum spanning tree where p = V and q = E. In this paper, we present an approach to solve the element perturbation problem of the s-optimum spanning tree in t(s)(p, q).
FINDING THE MOST VITAL EDGE WITH RESPECT TO K-TERMINAL RELIABILITY IN SERIES-PARALLEL NETWORKS
(1993-09-01)
WANG, PF
;
HSU, LH
;
資訊工程學系
;
Department of Computer Science
Let K be contained in the vertex-set of a graph G. ''The most vital edge'' is the edge whose deletion yields the largest decrease in the K-terminal reliability, that is the probability that all vertices in K are connected. In this paper, we present a linear-time algorithm for finding the most vital edge with respect to K-terminal reliability in series-parallel networks.
FINDING THE MOST VITAL EDGE WITH RESPECT TO MINIMUM SPANNING TREE IN WEIGHTED GRAPHS
(1991-09-13)
HSU, LH
;
JAN, RH
;
LEE, YC
;
HUNG, CN
;
CHERN, MS
FINDING THE MOST VITAL EDGES WITH RESPECT TO THE NUMBER OF SPANNING-TREES
(1994-12-01)
TSEN, FSP
;
SUNG, TY
;
LIN, MY
;
HSU, LH
;
MYRVOLD, W
A most vital edge of a graph (w.r.t. the spanning trees) is an edge whose deletion most drastically decreases the number of spanning trees. We present an algorithm for determining the most vital edges based on Kirchoff's matrix-tree theorem whose asymptotic time-complexity can be reduced to that of the fastest matrix multiplication routine, currently 0(n(2.376)). The foundation for this approach is a more general algorithm for directed graphs for counting the rooted spanning arborescences containing each of the arcs of a digraph. A network can be modeled as a probabilistic graph. Under one such model proposed by Kel'mans, the all-terminal network reliability, maximizing the number of spanning trees is critical to maximizing reliability when edges are very unreliable. For this model, the most vital edges characterize the locations where an improvement of the reliability of the link most improves the reliability of the network.
GENERALIZED HOMOMORPHISM GRAPH FUNCTIONS
(1990-08-01)
HSU, LH
;
應用數學系
;
資訊工程學系
;
Department of Applied Mathematics
;
Department of Computer Science
MAXIMUM INDEPENDENT NUMBER FOR SERIES-PARALLEL NETWORKS
(1991-07-01)
HSU, LH
;
WANG, SY
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
A series-parallel network is used as a model of electric circuits. Usually, we use a series-parallel graph to represent a series-parallel network. However, there are a lot of different graph representations for a single series-parallel network. For a given graph, a subset of V(G) is called an independent set if there are no edge of G joining two vertices in S. An independent set S of G is maximum if G has no independent set S' with S' > S. The number of vertices in a maximum independent set of G is called the independent number of G and is denoted by alpha-(G). The maximum independent number alpha-(N) for a series-parallel network N is defined to be the maximum alpha(G[N]) among all possible graph representations G[N]. In this paper, we are going to present a linear time algorithm to compute alpha(N) for any series-parallel network N.
ON A MULTIPLICATIVE GRAPH FUNCTION CONJECTURE
(1983)
HSU, LH
;
交大名義發表
;
應用數學系
;
National Chiao Tung University
;
Department of Applied Mathematics
PARALLEL ALGORITHMS FOR FINDING THE MOST VITAL EDGE WITH RESPECT TO MINIMUM SPANNING TREE
(1992)
HSU, LH
;
WANG, PF
;
WU, CT
;
資訊工程學系
;
Department of Computer Science
Given a weighted graph G, the weight of a spanning tree T, denoted by w(T), is defined as the total weight of all edges in T. A spanning tree T in G is called a minimum spanning tree if w(T) less-than-or-equal-to w(T') for all spanning trees T' in G. Let w(G) denote the weight of the minimum spanning tree of G if G is connected; otherwise, w(G) = infinity. An edge e is called a most vital edge in G if w(G - e) greater-than-or-equal-to w(G - e') for every edge e' of G where G - e' denotes the partial graph obtained by removing e' from G. In this paper, we present several cost-optimal parallel algorithms, under different computation models, to find the most vital edge in a weighted graph.
PARALLEL ALGORITHMS FOR FINDING THE MOST VITAL EDGE WITH RESPECT TO MINIMUM SPANNING TREE
(1992-01-01)
HSU, LH
;
WANG, PF
;
WU, CT
;
資訊工程學系
;
Department of Computer Science
PARALLEL ALGORITHMS FOR FINDING THE MOST VITAL EDGE WITH RESPECT TO MINIMUM SPANNING TREE
(1992-01-01)
HSU, LH
;
WANG, PF
;
WU, CT
;
資訊工程學系
;
Department of Computer Science
The weight of a weighted graph G, w(G), is defined to be the weight of its minimum spanning tree. An edge e is called a most vital edge in G if w(G - e) greater-than-or-equal-to w(G - e') for every edge e' of G. In this paper, we present several cost-optimal parallel algorithms, under different computation models, to find the most vital edge in a weighted graph.
PARALLEL ALGORITHMS FOR FINDING THE MOST VITAL EDGE WITH RESPECT TO MINIMUM SPANNING TREE
(1992)
HSU, LH
;
WANG, PF
;
WU, CT
;
資訊工程學系
;
Department of Computer Science
The weight of a weighted graph G, w(G), is defined to be the weight of its minimum spanning tree. An edge e is called a most vital edge in G if w(G - e) greater-than-or-equal-to w(G - e') for every edge e' of G. In this paper, we present several cost-optimal parallel algorithms, under different computation models, to find the most vital edge in a weighted graph.
THE MOST VITAL EDGES OF MATCHING IN A BIPARTITE GRAPH
(1993-07-01)
HUNG, CN
;
HSU, LH
;
SUNG, TY
;
資訊工程學系
;
Department of Computer Science
Let G = (VE) be an undirected graph having an edge weight w(e) greater-than-or-equal-to 0 for each e is-an-element-of E. An edge is called a most vital edge (with respect to weighted matching) if its removal from G results in the largest decrease in the total weight of the maximum weighted matching. In this paper, we study the most vital edges of matching in a weighted bipartite graph. We present an 0(n3) algorithm to obtain the most vital edges.
THE MOST VITAL EDGES WITH RESPECT TO THE NUMBER OF SPANNING-TREES IN 2-TERMINAL SERIES-PARALLEL GRAPHS
(1992)
JAN, RH
;
HSU, LH
;
LEE, YY
;
資訊工程學系
;
Department of Computer Science
A set E' of k edges in a multigraph G = (V, E) is said to be a k most vital edge set (k-MVE set) if these edges being removed from G, the resultant graph G' = (V,E - E') has minimum number of spanning trees. The problem of finding a k-MVE set for two-terminal series-parallel graphs is considered in this paper. We present an O(Absolute value of E) time algorithm for the case k = 1, and an O(Absolute value of V(k) + Absolute value of E) time algorithm for arbitrary k.