Browsing by Author "Yan, JH"

Now showing 1 - 6 of 6

Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
(1996-05-20)
Chang, MS
;
Chen, YH
;
Chang, GJ
;
Yan, JH
;
應用數學系
Suppose G=(V,E) is a graph in which each maximal clique C-i is associated with an integer r(i), where 0 less than or equal to r(i) less than or equal to\C-i\. The generalized clique transversal problem is to determine the minimum cardinality of a subset D of V such that \D boolean AND C-i\greater than or equal to r(i) for every maximal clique C-i of G. The problem includes the clique-transversal problem, the i,1 clique-cover problem, and for perfect graphs, the maximum q-colorable subgraph problems as special cases. This paper gives complexity results for the problem on subclasses of chordal graphs, e.g., strongly chordal graphs, k-trees, split graphs, and undirected path graphs.
Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
(1996-05-20)
Chang, MS
;
Chen, YH
;
Chang, GJ
;
Yan, JH
;
應用數學系
Suppose G=(V,E) is a graph in which each maximal clique C-i is associated with an integer r(i), where 0 less than or equal to r(i) less than or equal toC-i. The generalized clique transversal problem is to determine the minimum cardinality of a subset D of V such that D boolean AND C-igreater than or equal to r(i) for every maximal clique C-i of G. The problem includes the clique-transversal problem, the i,1 clique-cover problem, and for perfect graphs, the maximum q-colorable subgraph problems as special cases. This paper gives complexity results for the problem on subclasses of chordal graphs, e.g., strongly chordal graphs, k-trees, split graphs, and undirected path graphs.
k-path partitions in trees
(1997-10-21)
Yan, JH
;
Chang, GJ
;
Hedetniemi, SM
;
Hedetniemi, ST
;
應用數學系
For a fixed positive integer k, the k-path partition problem is to partition the vertex set of a graph into the smallest number of paths such that each path has at most k vertices. The 2-path partition problem is equivalent to the edge-cover problem. This paper presents a linear-time algorithm for the k-path partition problem in trees. The algorithm is applicable to the problem of finding the minimum number of message originators necessary to broadcast a message to all vertices in a tree network in one or two time units.
Quasi-threshold graphs
(1996-08-27)
Yan, JH
;
Chen, JJ
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
Quasi-threshold graphs are defined recursively by the following rules: (1) K-1 is a quasi-threshold graph, (2) adding a new vertex adjacent to all vertices of a quasi-threshold graph results in a quasi-threshold graph, (3) the disjoint union of two quasi-threshold graphs is a quasi-threshold graph. This paper gives some new equivalent definitions of a quasi-threshold graph. From them, linear time recognition algorithms follow. We also give linear time algorithms for the edge domination problem and the bandwidth problem in this class of graphs.
Signed degree sequences of signed graphs
(1997-10-01)
Yan, JH
;
Lih, KW
;
Kuo, D
;
Chang, GJ
;
應用數學系
This paper gives necessary and sufficient conditions for an integral sequence to be the signed degree sequence of a signed graph or a signed tree, answering a question raised by Chartrand et al. (1994). (G. Chartrand, H. Gavlas, F. Harary, and M. Schultz, On signed degrees in signed graphs, Czech. Math. J.44 (1994), 677-690). (C) 1997 John Wiley & Sons, Inc.
Signed degree sequences of signed graphs
(1997-10-01)
Yan, JH
;
Lih, KW
;
Kuo, D
;
Chang, GJ
;
應用數學系
This paper gives necessary and sufficient conditions for an integral sequence to be the signed degree sequence of a signed graph or a signed tree, answering a question raised by Chartrand et al. (1994). (G. Chartrand, H. Gavlas, F. Harary, and M. Schultz, On signed degrees in signed graphs, Czech. Math. J.44 (1994), 677-690). (C) 1997 John Wiley & Sons, Inc.