Browsing by Author "TAN, JJM"

Now showing 1 - 5 of 5

A GENERALIZATION OF THE STABLE MATCHING PROBLEM
(1995-04-21)
TAN, JJM
;
HSUEH, YC
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
It is known that there may not exist any stable matching for a given instance of the stable roommates problem. A stable partition is a structure that generalizes the notion of a stable matching; Tan (1991) proved that every instance of the stable roommates problem contains at least one such structure. In this paper we propose a new algorithm for finding a stable partition, and hence a new algorithm for finding a stable matching if one exists. Our algorithm processes the problem dynamically as long as certain relative preference orders are maintained. Some theoretical results about stable partitions are also presented.
A MAXIMUM STABLE MATCHING FOR THE ROOMMATES PROBLEM
(1990)
TAN, JJM
;
資訊工程學系
;
Department of Computer Science
The stable roommates problem is that of matching n people into n/2 disjoint pairs so that no two persons, who are not paired together, both prefer each other to their respective mates under the matching. Such a matching is called "a complete stable matching". It is known that a complete stable matching may not exist. Irving proposed an O(n2) algorithm that would find one complete stable matching if there is one, or would report that none exists. Since there may not exist any complete stable matching, it is natural to consider the problem of finding a maximum stable matching, i.e., a maximum number of disjoint pairs of persons such that these pairs are stable among themselves. In this paper, we present an O(n2) algorithm, which is a modified version of Irving's algorithm, that finds a maximum stable matching.
A NECESSARY AND SUFFICIENT CONDITION FOR THE EXISTENCE OF A COMPLETE STABLE MATCHING
(1991-03-01)
TAN, JJM
;
資訊工程學系
;
Department of Computer Science
MINIMUM RECTANGULAR PARTITION PROBLEM FOR SIMPLE RECTILINEAR POLYGONS
(1990-07-01)
LIOU, WT
;
TAN, JJM
;
LEE, RCT
;
資訊工程學系
;
Department of Computer Science
STABLE MATCHINGS AND STABLE PARTITIONS
(1991)
TAN, JJM
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
;
Department of Computer Science