44728169
A New Game Chromatic Number
Consider the following two-person game on a graphG.Players I and II move alternatively to color a yet uncolored vertex ofGproperly using a pre-specified set of colors. Furthermore, Player II can only use the colors that have been used, unless he is forced to use a new color to guarantee that the graph is colored properly. The game ends when some player can no longer move. Player I wins if all vertices ofGare colored. Otherwise Player II wins. What is the minimal number?g*(G)of colors such that Player I has a winning strategy? This problem is motivated by the game chromatic number?g(G)introduced by Bodlaender and by the continued work of Faigle, Kern, Kierstead and Trotter. In this paper, we show that?g*(T) ?3for each treeT.We are also interested in determining the graphsGfor which?(G)= ?g*(G),as well as?g*(G)for thek-inductive graphs wherekis a fixed positive integer.
43538481
Vertex-disjoint cycles containing specified vertices in a bipartite graph
A minimum degree condition is given for a bipartite graph to contain a 2-factor each component of which contains a previously specified vertex. 2004 Wiley Periodicals, Inc. J Graph Theory 46: 145–166, 2004
9764979
Tough enough chordal graphs are Hamiltonian
3744350
Hamiltonian graphs involving neighborhood unions
Dirac proved that a graph G is hamiltonian if the minimum degree δ(G) ≥ n/2, where n is the order of G. Let G be a graph and A ⊆ V(G). The neighborhood of A is N(A) = {b : ab ∈ E(G) for some a ∈ A}. For any positive integer k, we show that every (2k − 1)-connected graph of order n ≥ 16k is hamiltonian if |N(A)| ≥ n/2 for every independent vertex set A of k vertices. The result contains a few known results as special cases. The case of k = 1 is the classic result of Dirac when n is large and the case of k = 2 is a result of Broersma, Van den Heuvel, and Veldman when n is large. For general k, this result improves a result of Chen and Liu. The lower bound 2k − 1 on connectivity is best possible in general while the lower bound 16k for n is conjectured to be unnecessary. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 83–100, 2006
3811952
Degree Sequences with Repeated Values
A given nonincreasing sequence D = (d1, d2, · · · , dn) is said to contain a (nonincreasing) repetition sequence D∗ = (di1 , di2 , · · · , dik ) for some k ≤ n − 2 if all values of D −D∗ are distinct and for any dil ∈ D ∗ there exists some dt ∈ D −D∗ such that dil = dt. For any pair of integers n and k with n ≥ k + 2, we investigate the existence of a graphic sequence which contains a given repetition sequence. Our main theorem contains the known results for the special case di1 = dik if k = 1 or k = 2 (see [1, 5, 2]). 1supported in part by a foundation of Academia Sinica.
39660968
A special k-coloring for a connected k-chromatic graph
For each positive integer k we consider the smallest positive integer f(k) (dependent only on k) such that the following holds: Each connected graph G with chromatic number ?(G) = k can be properly vertex colored by k colors so that for each pair of vertices xo and xp in any color class there exist vertices x1, x2, ?, xp-1 of the same class with dist(xi, xi+1) ? f(k) for each i, 0 ? i ? p ? 1. Thus, the graph is k-colorable with the vertices of each color class placed throughout the graph so that no subset of the class is at a distance > f(k) from the remainder of the class.We prove that f(k) < 12k when the order of the graph is ? k(k ? 2) + 1.
45776383
Efficient Parallel Algorithms for Doubly Convex-Bipartite Graphs
Suppose that G = (S, T, E) is a bipartite graph. An ordering of S(T) has the adjacency property if for each vertex in T(S), its adjacent vertices in S(T) are consecutive in the ordering. If there exist orderings of S and T which have the adjacency property, G is called a doubly convex-bipartite graph. In this paper, a parallel algorithm is proposed to recognize a doubly convex-bipartite graph. The algorithm runs in O(log n) time using O(n3log n) processors on the CRCW PRAM, or O(log2 n) time using O(n3log2 n) processors on the CREW PRAM.
40869256
Parallel algorithms for permutation graphs
In this paper, parallel algorithms are presented for solving some problems on permutation graphs. The coloring problem is solved inO(log2n) time usingO(n3/logn) processors on the CREW PRAM, orO(logn) time usingO(n3) processors on the CRCW PRAM. The weighted clique problem, the weighted independent set problem, the cliques cover problem, and the maximal layers problem are all solved with the same complexities. We can also show that the longest common subsequence problem belongs to the class NC.
13431767
A compiler approach for reducing data cache energy
Silicon technology advances have made it possible to pack millions of transistors --- switching at high clock speeds --- on a single chip. While these advances bring unprecedented performance to electronic products, they pose difficult power/energy consumption problems. For example, large number of transistors in dense on-chip cache memories consume significant static (leakage) power even if the cache is not used by the current computation. While previous compiler research studied code and data restructuring for improving data cache performance, to our knowledge, there is no compiler-based study that targets data cache leakage power consumption. In this paper, we present code restructuring techniques for array-based and pointer-intensive applications for reducing data cache energy consumption. The idea is to let the compiler to analyze the code and insert instructions that turn off cache lines that keep variables not used by the current computation. This turning off does not destroy contents of a cache line, and waking up the cache line incurs very little overhead. Due to data locality, we find that at a given time only a small portion of the data cache needs to be active; the remaining part can be placed into a leakage-saving mode (state); i.e., they can be turned off. Our preliminary results indicate that the proposed strategy reduces the cache energy consumption significantly. We also show that several compiler optimizations increase the effectiveness of our strategy.
17483991
Energy-aware computation duplication for improving reliability in embedded chip multiprocessors
Compilers designed for current embedded systems must be capable of addressing multiple constraints such as low power, high performance, small memory footprint and form factor, and high reliability at the same time. In particular, optimizing for one constraint should be performed carefully, considering its impact on other constraints. Recent trends indicate that transient errors are becoming increasingly important in embedded systems. Focusing on an embedded chip multiprocessor and array-intensive applications, this paper demonstrates how reliability against transient errors can be improved without impacting execution time by utilizing idle processors for duplicating some of the computations of the active processors. It also shows how a balance between power savings and reliability improvement can be struck using a metric called the energy-delay-fallibility product. Our experimental results indicate that the "percentage of duplicated computations" is a useful high-level metric for studying the tradeoffs among performance, power, and reliability
14750422
Reducing power with performance constraints for parallel sparse applications
Sparse and irregular computations constitute a large fraction of applications in the data-intensive scientific domain. While every effort is made to balance the computational workload in such computations across parallel processors, achieving sustained near machine-peak performance with close-to-ideal load balanced computation-to-processor mapping is inherently difficult. As a result, most of the time, the loads assigned to parallel processors can exhibit significant variations. While there have been numerous past efforts that study this imbalance from the performance viewpoint, to our knowledge, no prior study has considered exploiting the imbalance for reducing power consumption during execution. Power consumption in large-scale clusters of workstations is becoming a critical issue as noted by several recent research papers from both industry and academia. Focusing on sparse matrix computations in which underlying parallel computations and data dependencies can be represented by trees, this paper proposes schemes that save power through voltage/frequency scaling. Our goal is to reduce overall energy consumption by scaling the voltages/frequencies of those processors that are not in the critical path; i.e., our approach is oriented towards saving power without incurring performance penalties.