22789583
Disjoint directed quadrilaterals in a directed graph
Let D be a directed graph of order 4k, where k is a positive integer. Suppose that the minimum degree of D is at least 6k 2. We show that D contains k disjoint directed quadrilaterals with only one exception. 2005 Wiley Periodicals, Inc. J Graph Theory 50: 91–104, 2005
34464594
On Quadrilaterals and Cycle Covers in a Bipartite Graph
5245849
On Independent Cycles in a Bipartite Graph
Abstract. Let G=(V1,V2;E) be a bipartite graph with 2k≤m=|V1|≤|V2|=n, where k is a positive integer. We show that if the number of edges of G is at least (2k−1)(n−1)+m, then G contains k vertex-disjoint cycles, unless e(G)=(2k−1)(n−1)+m and G belongs to a known class of graphs.
12358667
On Covering a Bipartite Graph with Cycles
We conjectured in [H. Wang, Australas. J. Combin., 19 (1999), pp. 115--121] that, for each integer $k\geq 2$, there exists N(k) such that if G=(V1,V2;E) is a bipartite graph with $|V_1|=|V_2|=n\geq N(k)$ and d(x)+d(y)\geq n+k$ for each pair of nonadjacent vertices x and y of G with $x\in V_1$ and $y\in V_2$, then for any k independent edges e1, . . ., ek of G, there exist k vertex-disjoint cycles C1, . . . ,Ck in G such that $e_i\in E(C_i)$ for all $i\in\{1,\ldots ,k\}$ and $V(C_1\cup\cdots \cup C_k)=V(G)$. This conjecture is also verified for k=2 in [H. Wang, Australas. J. Combin., 19 (1999), pp. 115--121]. We prove this conjecture for k=3 in this paper.
36127171
Packing Three Copies of a Tree into a Complete Graph
Abstract A three T of order n is said to be 3-placeable if there are three edge-disjoint copies of T in Kn. In this paper we characterize all the trees T such that T is 3-placeable.
9527664
Vertex-Disjoint Triangles in Claw-Free Graphs with Minimum Degree at Least Three
. Our main result is as follows: For any integer , if G is a claw-free graph of order at least and with minimum degree at least 3, then G contains k vertex-disjoint triangles unless G is of order and G belongs to a known class of graphs. We also construct a claw-free graph with minimum degree 3 on n vertices for each such that it does not contain k vertex-disjoint triangles. We put forward a conjecture on vertex-disjoint triangles in -free graphs.
36856889
Prime Cube Graph Approach for Processor Allocation in Hypercube Multiprocessors
661328
Physical experimentation with prefetching helper threads on Intel's hyper-threaded processors
Pre-execution techniques have received much attention as an effective way of prefetching cache blocks to tolerate the ever-increasing memory latency. A number of pre-execution techniques based on hardware, compiler, or both have been proposed and studied extensively by researchers. They report promising results on simulators that model a simultaneous multithreading (SMT) processor. We apply the helper threading idea on a real multithreaded machine, i.e., Intel Pentium 4 processor with hyper-threading technology, and show that indeed it can provide wall-clock speedup on real silicon. To achieve further performance improvements via helper threads, we investigate three helper threading scenarios that are driven by automated compiler infrastructure, and identify several key challenges and opportunities for novel hardware and software optimizations. Our study shows a program behavior changes dynamically during execution. In addition, the organizations of certain critical hardware structures in the hyper-threaded processors are either shared or partitioned in the multithreading mode and thus, the tradeoffs regarding resource contention can be intricate. Therefore, it is essential to judiciously invoke helper threads by adapting to the dynamic program behavior so that we can alleviate potential performance degradation due to resource contention. Moreover, since adapting to the dynamic behavior requires frequent thread synchronization, having light-weight thread synchronization mechanisms is important.
9404376
An XML-Based Implementation of Multimodal Affective Annotation
In simple cases, affective computing is a computational device recognizing and acting upon the emotions of its user or having (or simulating having) emotions of its own in complex cases. Multimodal technology is currently one of the hottest focuses in affective computing research. However, the lack of a large-scale multimodal database limits the research to some respective and scattered fields, such as affective recognition by video or by audio. This paper describes the development and implementation of an XML-based multimodal affective annotation system which is called MAAS (Multimodal Affective Annotation System). MAAS contains a hierarchical affective annotation model based on the 3-dimensional affect space derived from Mehrabian’s PAD temperament scale. The final annotation file is formed in XML format in order to interchange the resources with other research groups conveniently.
19517380
PAD Model Based Facial Expression Analysis
The validity of PAD (Pleasure-Arousal-Dominance) theory in vision area and the feasibilityT on PAD based models for facial expression analysis are discussed in this paper. Three new models based on PAD theory are proposed and their feasibility is verified by experiments on Cohn-Kanade dataset and PAD dataset which is collected from well-designed psychological experiments. After combining Gabor feature and SVM (Support Vector Machine), the result can be further improved. Compared with the basic expression models, our experiments show that the predominance of PAD based model is that it can represent almost any states of expression. Finally, our preliminary experiments show that distinguishing different grades of the same expression is promising by our models.
29063745
A New Graph Approach to Minimizing Processor Fragmentation in Hypercube Multiprocessors
The authors propose a new approach for subcube and noncubic processor allocations for hypercube multiprocessors. The main idea is to represent available processors in the system by means of a prime cube graph (PC-graph). The PC-graph maintains the inter-relationships between free subcubes and hence reduces both internal and external processor fragmentations. Their simulation results show that the PC-graph approach outperforms the existing allocation strategies by 25% to 50% under certain load conditions. >