Browsing by Author "CHANG, GJ"

Now showing 1 - 13 of 13

ALGORITHMIC ASPECTS OF NEIGHBORHOOD NUMBERS
(1993-02-01)
CHANG, GJ
;
FARBER, M
;
TUZA, Z
;
應用數學系
;
Department of Applied Mathematics
In a graph G = (V, E), E[v] denotes the set of edges in the subgraph induced by N[v] = {v} or {u is-an-element-of V: uv is-an-element-of E}. The neighborhood-covering problem is to find the minimum cardinality of a set C of vertices such that E = or {E[v]: v is-an-element-of C}. The neighborhood-independence problem is to find the maximum cardinality of a set of edges in which there are no two distinct edges belonging to the same E[v] for any v is-an-element-of V. Two other related problems are the clique-transversal problem and the clique-independence problem. It is shown that these four problems are NP-complete in split graphs with degree constraints and linear time algorithms for them are given in a strongly chordal graph when a strong elimination order is given.
AN EXISTENCE THEOREM FOR ABSTRACT STABLE SETS
(1991-12-01)
CHANG, C
;
CHANG, GJ
;
應用數學系
;
Department of Applied Mathematics
We provide an existence theorem for stable sets which is equivalent to Zorn's lemma and study the connections between the unique stable set for majorization and the stable sets for the dominance relation.
AN UPPER BOUND FOR THE TRANSVERSAL NUMBERS OF 4-UNIFORM HYPERGRAPHS
(1990-10-01)
LAI, FC
;
CHANG, GJ
;
應用數學系
;
Department of Applied Mathematics
CENTERS OF CHORDAL GRAPHS
(1991)
CHANG, GJ
;
應用數學系
;
Department of Applied Mathematics
In a graph G = (V, E), the eccentricity e(S) of a subset S is contained in or equal to V is max(x is-an-element-of V) min(y is-an-element-of S) d(x, y); and e(x) stands for e({x}). The diameter of G is max(x is-an-element-of V) e(x), the radius r(G) of G is min(x is-an-element-of V) e(x) and the clique radius cr(G) is min e(K) where K runs over all cliques. The center of G is the subgraph induced by C(G), the set of all vertices x with e(x) = r(G). A clique center is a clique K with e(K) = cr(G). In this paper, we study the problem of determining the centers of chordal graphs. It is shown that the center of a connected chordal graph is distance invariant, biconnected and of diameter no more than 5. We also prove that 2cr(G) less-than-or-equal-to d(G) less-than-or-equal-to 2cr(G) + 1 for any connected chordal graph G. This result implies a characterization of a biconnected chordal graph of diameter 2 and radius 1 to be the center of some chordal graph.
EDGE DOMATIC NUMBERS OF COMPLETE N-PARTITE GRAPHS
(1994)
HWANG, SF
;
CHANG, GJ
;
應用數學系
;
Department of Applied Mathematics
An edge dominating set of a graph is a set of edges D such that every edge not in D is adjacent to an edge in D. An edge domatic partition of a graph G = (V, E) is a collection of pairwise disjoint edge dominating sets of G whose union is E. The maximum size of an edge domatic partition of G is called the edge domatic number of G. In this paper we study the edge domatic numbers of complete n-partite graphs. In particular, we give exact values for the edge domatic numbers of complete 3-partite graphs and balanced complete n-partite graphs with odd n.
SET TO SET BROADCASTING IN COMMUNICATION-NETWORKS
(1992-12-14)
LEE, HM
;
CHANG, GJ
;
應用數學系
;
Department of Applied Mathematics
Suppose G = (V,E) is a graph whose vertices represent people and edges represent telephone lines between pairs of people. Each person knows a unique message and is ignorant of the messages of other people at the beginning. These messages are then spread by telephone calls. In each call, two people exchange all information they have so far in exactly one unit of time. Suppose A and B are two nonempty subsets of V. The main purpose of this paper is to study the minimum number b(A,B,G) of telephone calls by which A broadcasts to B; and the minimum time t(A,B,G) such that A broadcasts to B. In particular, we give an exact formula for b(A,B,K(n)) and linear-time algorithms for computing b(A,B,T) and t(A,B,T) of a tree T.
THE DOMATIC NUMBER PROBLEM
(1994-02-15)
CHANG, GJ
;
交大名義發表
;
應用數學系
;
National Chiao Tung University
;
Department of Applied Mathematics
A dominating set of a graph G=(V,E) is a subset D of V such that every vertex not in D is adjacent to some vertex in D. The domatic number d(G) of G is the maximum positive integer k such that V can be partitioned into k pairwise disjoint dominating sets. The purpose of this paper is to study the domatic numbers of graphs that are obtained from small graphs by performing graph operations, such as union, join and Cartesian product.
THE DOMATIC NUMBER PROBLEM IN INTERVAL-GRAPHS
(1990-11-01)
LU, TL
;
HO, PH
;
CHANG, GJ
;
交大名義發表
;
應用數學系
THE K-NEIGHBOR DOMINATION PROBLEM
(1991-06-17)
HWANG, SF
;
CHANG, GJ
;
應用數學系
;
Department of Applied Mathematics
As a model of certain location problem, we consider the following domination problem. The k-neighbor domination problem is to select a minimum cardinality vertex set D of a graph G = (V, E) such that every vertex x not in D is adjacent to at least k vertices in D. This paper presents a linear algorithm to solve the problem for block graphs. For any fixed k, we also prove that the k-neighbor domination problem is NP-complete for some classes of graphs.
THE PATH-PARTITION PROBLEM IN BLOCK GRAPHS
(1994-12-23)
YANG, JH
;
CHANG, GJ
;
應用數學系
;
Department of Applied Mathematics
We present a linear-time algorithm for the path-partition problem in block graphs.
THE PROFILE MINIMIZATION PROBLEM IN TREES
(1994-02-01)
KUO, D
;
CHANG, GJ
;
交大名義發表
;
應用數學系
;
National Chiao Tung University
The profile minimization problem is to find a one-to-one function f from the vertex set V(G) of a graph G to the set of all positive integers such that SIGMA(x is-an-element-of V(G)){(f(x) - min(y is-an-element-of N[x]) f(y)} is as small as possible, where N[x] = {x} or {y : y is adjacent to x} is the closed neighborhood of x in G. This paper gives an O(n1.722) time algorithm for the problem in a tree of n vertices.
THE W-MEDIAN OF A CONNECTED STRONGLY CHORDAL GRAPH
(1994-11-01)
LEE, HY
;
CHANG, GJ
;
交大名義發表
;
應用數學系
;
National Chiao Tung University
Suppose G = (V,E) is a graph in which every vertex x has a non-negative real number w(x) as its weight. The w-distance sum of a vertex y is D(G,W)(y) = SIGMA(xis-an-element-ofV) d(y,x)w(x). The w-median of G is the set of all vertices y with minimum w-distance sum D(G,W)(y). This paper shows that the w-median of a connected strongly chordal graph G is a clique when w(x) is positive for all vertices x in G. (C) 1994 John Wiley & Sons, Inc.
WEIGHTED INDEPENDENT PERFECT DOMINATION ON COCOMPARABILITY GRAPHS
(1995-12-08)
CHANG, GJ
;
RANGAN, CP
;
COORG, SR
;
應用數學系
;
Department of Applied Mathematics
Suppose G = (V, E) is a graph in which every vertex v is an element of V is associated with a cost c(v). This paper studies the weighted independent perfect domination problem on G, i.e., the problem of finding a subset D of V such that every vertex in V is equal or adjacent to exactly one vertex in D and Sigma{c(v): v is an element of D} is minimum. We give an O(VE) algorithm for the problem on cocomparability graphs. The algorithm can be implemented to run in O(V(2.37)) time. With some modifications, the algorithm yields an O(V + E) algorithm on interval graphs, which are special cocomparability graphs.