Browsing by Author "Yeh, HG"

Now showing 1 - 6 of 6

A simple and direct derivation for the number of noncrossing partitions
(1998-06-01)
Liaw, SC
;
Yeh, HG
;
Hwang, FK
;
Chang, GJ
;
應用數學系
Kreweras considered the problem of counting noncrossing partitions of the set {1, 2, ..., n}, whose elements are arranged into a cycle in its natural order, into p parts of given sizes n(1), n(2), ..., n(p) (but not specifying which part gets which size). He gave a beautiful and surprising result whose proof resorts to a recurrence relation. In this paper we give a direct, entirely bijective, proof starting from the same initial idea as Kreweras' proof.
Domination in distance-hereditary graphs
(2002-01-15)
Chang, MS
;
Wu, SC
;
Chang, GJ
;
Yeh, HG
;
應用數學系
The domination problem and its variants have been extensively studied in the literature. In this paper we investigate the domination problem in distance-hereditary graphs, In particular, we give a linear-time algorithm for the domination problem in distance-hereditary graphs by a labeling approach. We actually solve a more general problem, called the L-domination problem, which also includes the total domination problem as a special case. (C) 2002 Elsevier Science B.V. All rights reserved.
Sortabilities of partition properties
(1999)
Chang, GJ
;
Chen, FL
;
Huang, LL
;
Hwang, FK
;
Nuan, ST
Consider the partition of a set of integers into parts. Various partition properties have been proposed in the literature to facilitate the restriction of the focus of attention to some small class of partitions. Recently, Hwang, Rothblum and Yao defined and studied the sortability of these partition properties as a tool to prove the existence of a partition with such a property in a given family. In this paper we determine the sortability indices of the seven most interesting properties of partitions providing a complete solution to the sortability issue.
The path-partition problem in bipartite distance-hereditary graphs
(1998-09-01)
Yeh, HG
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
A path partition of a graph is a collection of vertex-disjoint paths that cover all vertices of the graph. The path-partition problem is to find a path partition of minimum size. This paper gives a linear-time algorithm for the path-partition problem in bipartite distance-hereditary graphs.
Weighted connected domination and Steiner trees in distance-hereditary graphs
(1998-10-05)
Yeh, HG
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
Distance-hereditary graphs are graphs in which every two vertices have the same distance in every connected induced subgraph containing them. This paper studies distance-hereditary graphs from an algorithmic viewpoint. In particular, we present linear-time algorithms for finding a minimum weighted connected dominating set and a minimum vertex-weighted Steiner tree in a distance-hereditary graph. Both problems are NP-complete in general graphs. (C) 1998 Elsevier Science B.V. All rights reserved.
Weighted connected k-domination and weighted k-dominating clique in distance-hereditary graphs
(2001-07-28)
Yeh, HG
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
A graph is distance-hereditary if the distance between any two vertices in a connected induced subgraph is the same as in the original graph. This paper presents efficient algorithms for solving the weighted connected k-domination and the weighted k-dominating clique problems in distance-hereditary graphs, (C) 2001 Elsevier Science B.V. All rights reserved.