Browsing by Author "Wong, CK"

Now showing 1 - 4 of 4

A graph-theoretic sufficient condition for FPGA/FPIC switch-module routability
(1997)
Chang, YW
;
Wong, DF
;
Wong, CK
;
交大名義發表
;
資訊工程學系
Switch modules are the most important component of the routing resources in FPGA's/FPIC's. We consider in this paper an FPGA/FPIC switch-module analysis problem: The in puts consist of a switch-module description and the number of nets required to be routed through the switch module; the question is to determine if there exists a feasible routing for the routing requirements on the switch module. This problem is applicable to the routability evaluation of FPGA/FPIC switch modules, the switch-module design for FPGA's/FPIC's, and FPGA/FPIC routing. We present a graph-theoretic sufficient condition for the analysis problem. The implications of the condition are: (1) there exist several classes of efficient approximation algorithms for the analysis problem; (2) there exist several classes of switch-module architectures on which the analysis problem can be solved efficiently.
On k-ary spanning trees of tournaments
(1999-03-01)
Lu, XY
;
Wang, DW
;
Chang, GJ
;
Lin, IJ
;
Wong, CK
It is well known that every tournament contains a Hamiltonian path, which can be restated as that every tournament contains a unary spanning tree. The purpose of this article is to study the general problem of whether a tournament contains a k-ary spanning tree. In particular, we prove that, for any fixed positive integer k, there exists a minimum number h(k) such that every tournament of order at least h(k) contains a k-ary spanning tree. The existence of a Hamiltonian path for any tournament is the same as h(1) = 1. We then show that h(2) = 4 and h(3) = 8. The values of h(k) remain unknown for k greater than or equal to 4. (C) 1999 John Wiley & Sons. Inc. J Graph Theory 30: 167-176, 1999.
The K-r-packing problem
(2001)
Guruswami, V
;
Rangan, CP
;
Chang, MS
;
Chang, GJ
;
Wong, CK
For a fixed integer r greater than or equal to 2, the K-r-packing problem is to find the maximum number of pairwise vertex-disjoint K-r's (complete graphs on r vertices) in a given graph. The K-r-factor problem asks fur the existence of a partition of the vertex set of a graph into K-r's. The K-r-packing problem is a natural generalization of the classical matching problem, but turns out to be much harder for r greater than or equal to 3 - it is known that for r greater than or equal to 3 the K-r-factor problem is NP-complete: for graphs with clique number r [16]. This paper considers the complexity of the K-r-packing problem on restricted classes of graphs. We first prove that for r greater than or equal to 3 the K-r-packing problem is NP-complete even when restrict to chordal graphs, planar graphs (for r = 3. 4 only), line graphs acid total graphs. The hardness result for K-3- packing on chordal graphs answers an open question raised in [6]. We also give (simple) polynomial algorithms for the K-3-packing and the K-r-factor problems on split graphs (this is interesting in light of the fact that K-r-packing becomes NP-complete on split graphs for r greater than or equal to 4), and for the K-r-packing problem on cographs.
The vertex-disjoint triangles problem
(1998)
Guruswami, V
;
Rangan, CP
;
Chang, MS
;
Chang, GJ
;
Wong, CK
The vertex-disjoint triangles (VDT) problem asks for a set of maximum number of pairwise vertex-disjoint triangles in a given graph G. The triangle cover problem asks for the existence of a perfect triangle packing in a graph G. It is known that the triangle cover problem is NP-complete on general graphs with clique number 3 [6]. The VDT problem is MAX SNP-hard on graphs with maximum degree four, while it can be approximated within 3/2 + epsilon, for any epsilon > 0, in polynomial time [11]. We prove that the VDT problem is NP-complete even when the input graphs are chordal, planar, line or total graphs. We present an O(m root n) algorithm for the VDT problem on split graphs and an O(n(3)) algorithm for the VDT problem on cographs. A linear algorithm for the triangle cover problem on strongly chordal graphs is also presented. Finally, the notion of packing-hardness, which may be crucial to the understanding of the difficulty of generalized matching problems, is defined.