Browsing by Author "Chang, MS"

Now showing 1 - 15 of 15

A generalisation of consecutive k-out-of-n : G systems
(2000-06-01)
Lin, MS
;
Chang, MS
;
Chen, DJ
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
A generalized class of consecutive-k-out-of-n:G systems, referred to as Con/k*/n:G systems, is studied. A Con/k*/n:G system has n ordered components and is good if and only if ki good consecutive components that originate at component i are all good, where k(i) is a function of i. Theorem 1 gives an O(n) time equation to compute the reliability of a linear system and Theorem 2 gives an O(n(2)) time equation for a circular system. A distributed computing system with a linear (ring) topology is an example of such system. This application is very important, since for other classes of topologies, such as general graphs, planar graphs, series-parallel graphs, tree graphs, and star graphs, this problem has been proven to be NP-hard.
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.
Distributed-program reliability analysis: Complexity and efficient algorithms
(1999-03-01)
Lin, MS
;
Chang, MS
;
Chen, DJ
;
資訊工程學系
;
Department of Computer Science
This paper investigates the problem of distributed-program reliability in various classes of distributed computing systems. This problem is computationally intractable for arbitrary distributed computing systems, even when it is restricted to the class of star distributed computing systems. One solvable case for star distributed computing systems is identified, in which data files are distributed with respective to a consecutive property; a polynomial-time algorithm is developed for this case. A linear-time algorithm is developed to test whether or not an arbitrary star distributed computing system has this consecutive file distribution property. Efficient algorithms may still be sought for computing lower & upper bounds on the distributed program reliability for arbitrary distributed computing systems.
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.
Efficient algorithms for reliability analysis of distributed computing systems
(1999-07-01)
Lin, MS
;
Chang, MS
;
Chen, DJ
;
資訊工程學系
;
Department of Computer Science
A distributed computing system is modeled as a collection of resources (e.g. processing elements, data tiles and programs) interconnected via an arbitrary communication network and controlled by a distributed operating system, The distributed program reliability in a distributed computing system is the probability of successful execution of a program running on multiple processing elements and needs to retrieve data files from other processing elements. This reliability varies according to (1) the topology of the distributed computing system, (2) the reliability of the communication edges, (3) the data files and programs distribution among processing elements and (4) the data files required to execute a program. In addition, computing the reliability of distributed computing systems is #P-complete even when the distributed computing system is restricted to a series-parallel, a 2-tree, a tree, or a star structure. This paper presents efficient algorithms for computing the reliability of a distributed program running on other restricted classes of networks. (C) 1999 Elsevier Science Inc. All rights reserved.
ICA-based spatiotemporal approach for single-trial analysis of postmovement MEG beta synchronization
(2003-12-01)
Lee, PL
;
Wu, YT
;
Chen, LF
;
Chen, YS
;
Cheng, CM
The extraction of event-related oscillatory neuromagnetic activities from single-trial measurement is challenging due to the non-phase-locked nature and variability from trial to trial. The present study presents a method based on independent component analysis (ICA) and the use of a template-based correlation approach to extract Rolandic beta rhythm from magnetoencephalographic (MEG) measurements of right finger lifting. A single trial recording was decomposed into a set of coupled temporal independent components and corresponding spatial maps using ICA and the reactive beta frequency band for each trial identified using a two-spectrum comparison between the postmovement interval and a reference period. Task-related components survived dual criteria of high correlation with both the temporal and the spatial templates with an acceptance rate of about 80%. Phase and amplitude information for noise-free MEG beta activities were preserved not only for optimal calculation of beta rebound (event-related synchronization) but also for profound penetration into subtle dynamics across trials. Given the high signal-to-noise ratio (SNR) of this method, various methods of source estimation were used on reconstructed single-trial data and the source loci coherently anchored in the vicinity of the primary motor area. This method promises the possibility of a window into the intricate brain dynamics of motor control mechanisms and the cortical pathophysiology of movement disorder on a trial-by-trial basis. (C) 2003 Elsevier Inc. All rights reserved.
Multimedia task reliability analysis based on token ring network
(1996)
Chen, DJ
;
Chang, MS
;
Yang, CL
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
The distributed program reliability analysis on a star topology: Efficient algorithms and approximate solution
(1999-06-01)
Chang, MS
;
Chen, DJ
;
Lin, MS
;
Ku, KL
;
資訊科學與工程研究所
A distributed computing system consists of processing elements, communication links, memory units, data files, and programs. These resources are interconnected via a communication network and controlled by a distributed operating system. The distributed program reliability (DPR) in a distributed computing system is the probability that a program which runs on multiple processing elements and needs to retrieve data files from other processing elements will be executed successfully. This reliability varies according to 1) the topology of the distributed computing system, 2) the reliability of the communication edges, 3) the data files and programs distribution among processing elements, and 4) the data files required to execute a program. In this paper, we show that computing the distributed program reliability on a star distributed computing system is #P-complete. A polynomially solvable case is developed for computing the distributed program reliability when some additional file distribution is restricted on the star topology. We also propose a polynomial time algorithm for computing the distributed program reliability with approximate solutions when the star star topology has no the additional file distribution.
The distributed program reliability analysis on ring-type topologies
(2001-06-01)
Lin, MS
;
Chang, MS
;
Chen, DJ
;
Ku, KL
;
資訊科學與工程研究所
Distributed computing system (DCS) has become very popular for its high fault-tolerance, potential for parallel processing, and better reliability performance. One of the important issues in the design of the DCS is the reliability performance. Distributed program reliability (DPR) is addressed to obtain this reliability measure, In this paper, we propose a polynomial-time algorithm for computing the DPR of ring topology and show that solving the DPR problem on a ring of trees topology is NP-hard. (C) 2001 Elsevier Science Ltd. All rights reserved.
The distributed program reliability analysis on star topologies
(1998)
Chang, MS
;
Chen, DJ
;
Lin, MS
;
Ku, KL
;
資訊科學與工程研究所
In this paper, we show that computing the distributed program reliability on the star distributed computing systems is NP-hard We develop a polynomially solvable case to compute distributed program reliability when some additional file distribution is restricted on the star topology. We also propose a polynomial time algorithm for computing distributed program reliability with approximate solution when the star topology is nor satisfied with the additional file distribution.
The distributed program reliability analysis on star topologies
(2000-02-01)
Chang, MS
;
Chen, DJ
;
Lin, MS
;
Ku, KL
;
資訊科學與工程研究所
A distributed computing system consists of processing elements, communication links, memory units, data files, and programs. These resources are interconnected via a communication network and controlled by a distributed operating system. The distributed program reliability in a distributed computing system is the probability that a program which runs on multiple processing elements and needs to retrieve data files from other processing elements will be executed successfully. This reliability varies according to (1) the topology of the distributed computing system, (2) the reliability of the communication edges, (3) the data files and programs distribution among processing elements, and (4) the data files required to execute a program. In this paper, we show that computing the distributed program reliability on the star distributed computing systems is NP-hard. We also develop an efficiently solvable case to compute distributed program reliability when some additional file distribution is restricted on the star topology.
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.
Time-constrained distributed program reliability analysis
(1998-12-01)
Chen, DJ
;
Chang, MS
;
Sheng, MC
;
Horng, MS
;
資訊科學與工程研究所
In this paper, we propose an approach to the reliability analysis of distributed programs that addresses real-time constraints. Our approach is based on a model for evaluating transmission time, which allows us to find the time needed to complete execution of the program, task, or mission under evaluation. With information on time-constraints, the corresponding Markov state space can then be defined for reliability computation. To speed up the evaluation process and reduce the size of the Markov state space, several dynamic reliability-preserving reductions are developed. A simple distributed real-time system is used as an example to illustrate the feasibility and uniqueness of the proposed approach.