Browsing by Author "SUNG, TY"

Now showing 1 - 3 of 3

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.
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.
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.