36844780
Partition of a directed bipartite graph into two directed cycles
Abstract Let D = (V1, V2; A) be a directed bipartite graph with |V1| = |V2| = n ⩾ 2. Suppose that dD(x) + dD(y) ⩾ 3n + 1 for all x ϵ V1 and y ϵ V2. Then D contains two vertex-disjoint directed cycles of lengths 2n1 and 2n2, respectively, for any positive integer partition n = n1 + n2. Moreover, the condition is sharp for even n and nearly sharp for odd n.
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.
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.
206077177
Pentagons and cycle coverings
Let G be a graph of order n ≥ 5k + 2, where k is a positive integer. Suppose that the minimum degree of G is at least (n + k)/2 . We show that G contains k pentagons and a path such that they are vertexdisjoint and cover all the vertices of G. Moreover, if n ≥ 5k + 7, then G contains k + 1 vertex-disjoint cycles covering all the vertices of G such that k of them are pentagons. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 194–208, 2007
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.
30994252
An extension of a theorem on cycles containing specified independent edges
We give an alternative proof of a conjecture due to Wang (J. Graph Theory 26 (1997) 105) in a stronger form. The main theorem states that for any integer k ≥ 2 if G is a graph of order n ≥ 4k - 1 and d(u) + d(υ) ≥ n + 2k - 2 for each pair of non-adjacent vertices u and υ of G, then, for any k independent edges e1,... ,ek of G, there exist k vertex-disjoint cycles C1,..., Ck in G such that (i) ei ∈ E(Ci) for all 1 ≤ i ≤ k, (ii) V(C1)∪ ... ∪V(Ck) = V(G), and (iii) #{i ≤ k||Ci| a > n - 4k + 2). It strengthens the conjecture of Wang, which was first proven by Egawa et al. (Graphs Combin. 16 (2000) 81).
39698287
Analysis of DC characteristics of GaAs double heterojunction bipolar transistors (DHBTs) with a pseudomorphic GaAsSb base
Abstract In this paper, DC characteristics in GaAs DHBTs with pseudomorphic GaAsSb base layer are investigated using an analytical approach. Devices using different GaAs 1− x Sb x base thickness with different Sb compositions were simulated to gain an in-depth understanding on the effect of base layer design on the device DC performance. Our calculated results show that, in the GaAsSb base with high Sb composition, the strain plays a non-negligible role in determining the overall device performance. The reduction of B–E turn-on voltage using a large Sb composition of GaAs 1− x Sb x could be partially compensated by strain in the base. Furthermore, for the devices using high Sb composition, a thin base layer has to be used to ensure elastic strain. In order to maintain reasonable base conductivity that is critical for device microwave performance, high base doping is required. However, our simulation reveals a drastic reduction of DC gain with the increase in base doping, while a high emitter doping may be helpful for the compensation of the degradation of β. A proper design of the device structure by taking the aforementioned issues into account is important for improving device DC and microwave performance.
10777801
A Polygon Detection Algorithm for Robot Visual Servoing
The problem of detecting polygon structures in images arises in many applications, from building extraction to cryo-electron microscopy. In this paper, A polygon detection algorithm (PDA) based on line detection is proposed. First of all, we introduce a parallel thinning algorithm to eliminate useless feature points. Then the feature points are organized as disjoint feature contours. For each independent contour, we detect line segment candidates based on RANSAC algorithm. With these candidates, a polygon (triangle, rectangle or other polygons) is composed. Compared to the state-of-the-art shape detection algorithms, PDA is much faster and it can detect any polygons such as triangles, rectangles, etc. We introduce PDA to a 6DOFs robot visual servoing platform and the experimental results show that significant improvements in time efficiency and performance robustness of the proposed algorithm have been achieved.
2923490
Hardware Support for Prescient Instruction Prefetch
This paper proposes and evaluates hardware mechanisms for supporting prescient instruction prefetch — an approach to improving single-threaded application performance by using helper threads to perform instruction prefetch. We demonstrate the need for enabling store-to-load communication and selective instruction execution when directly pre-executing future regions of an application that suffer I-cache misses. Two novel hardware mechanisms, safe-store and YAT-bits, are introduced that help satisfy these requirements. This paper also proposes and evaluates .nite state machine recall, a technique for limiting pre-execution to branches that are hard to predict by leveraging a counted I-prefetch mechanism. On a research Itanium®SMT processor with next line and streaming I-prefetch mechanisms that incurs latencies representative of next generation processors, prescient instruction prefetch can improve performance by an average of 10.0% to 22% on a set of SPEC 2000 benchmarks that suffer significant I-cache misses. Prescient instruction prefetch is found to be competitive against even the most aggressive research hardware instruction prefetch technique: fetch directed instruction prefetch.
11169454
Best of both latency and throughput
This paper describes the tradeoff between latency performance and throughput performance in a power-constrained environment. We show that the key to achieving both excellent latency performance as well as excellent throughput performance is to dynamically vary the amount of energy expended to process instructions according to the amount of parallelism available in the software. We survey four techniques for achieving variable energy per instruction: voltage/frequency scaling, asymmetric cores, variable-size cores, and speculation control. We estimate the potential range of energies obtainable by each technique and conclude that a combination of asymmetric cores and voltage/frequency scaling offers the most promising approach to design a chip-level multiprocessor that can achieve both excellent latency performance and excellent throughput performance.
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. >