13312657
Feedback vertex sets in star graphs
In a graph G = (V, E), a subset F ⊂ V(G) is a feedback vertex set of G if the subgraph induced by V(G) \ F is acyclic. In this paper, we propose an algorithm for finding a small feedback vertex set of a star graph. Indeed, our algorithm can derive an upper bound to the size of the feedback vertex set for star graphs. Also by applying the properties of regular graphs, a lower bound can easily be achieved for star graphs.
29352440
Induced matchings in asteroidal triple-free graphs
An induced matching M of a graph G is a set of pairwise nonadjacent edges such that no two edges of M are joined by an edge in G. The problem of finding a maximum induced matching is known to be NP-hard even for bipartite graphs of maximum degree four. In this paper, we study the maximum induced matching problem on classes of graphs related to AT-free graphs. We first define a wider class of graphs called the line-asteroidal triple-free (LAT-free) graphs which contains AT-free graphs as a subclass. By examining the square of line graph of LAT-free graphs, we give a characterization of them and apply this for showing that the maximum induced matching problem and a generalization, called the maximum δ-separated matching problem, on LAT-free graphs can be solved in polynomial time. In fact, our result can be extended to the classes of graphs with bounded asteroidal index. Next, we propose a linear-time algorithm for finding a maximum induced matching in a bipartite permutation (bipartite AT-free) graph using the greedy approach. Moreover, we show that using the same technique the minimum chain subgraph cover problem on bipartite permutation graphs can be solved with the same time complexity.
6354183
A multithreaded concurrent garbage collector parallelizing the new instruction in Java
Parallel, multithreaded Java applications such as Web servers, database servers, and scientific applications are becoming increasingly prevalent. Most of them have high object instantiation rates through the new bytecode that is implemented in a garbage collection subsystem typically. For aforementioned applications, traditional garbage collectors are often the bottleneck that limits program performance and processor utilization on multiprocessor systems. They suffer from long garbage collection pauses (stop-the-world mark-sweep algorithm) or inability of collecting cyclic garbage (reference counting approach). Generational garbage collection, however, is based only on the weak generational hypothesis that most objects die young. In this paper, a new multithreaded concurrent generational garbage collector (MCGC) based on mark-sweep with the assistance of reference counting is proposed. The MCGC can take advantage of multiple CPUs in an SMP system and the merits or light weight processes. Furthermore, the long garbage collection pause can be reduced and the garbage collection efficiency can be enhanced.
18001825
Architectural support for dynamic memory management
Recent advances in software engineering, such as graphical user interfaces and object-oriented programming, have caused applications to become more memory intensive. These applications tend to allocate dynamic memory prolifically. Moreover, automatic dynamic memory reclamation (garbage collection, GC) has become a popular feature in modern programming languages. As a result, the time consumed by dynamic storage management can be up to one-third of the program execution time. This illustrates the need for a high-performance memory management scheme. This paper presents a top-level design and evaluation of the proposed instruction extensions to facilitate heap management.
234543
Reusable Internal Hardware Templates
This paper describes the framework of internal hardware templates. These reusable templates can be instantiated, inside the FPGA, to the required precision. Thus, the resource utilization of the target RCMs can be improved. Moreover, the configuration time can be eliminated after the first use of the template. The detail design is presented.
38166516
A Sufficient Condition for Quasi-Claw-Free Hamiltonian Graphs
There are several well-known and important hamiltonian results for claw-free graphs but only a few are concerned with quasi-claw-free graphs. In this note, we provide a new sufficient condition for quasi-claw-free hamiltonian graphs.
16368228
Color pattern recognition by quaternion correlation
It is popular to use the conventional correlation for pattern recognition. But when using the conventional correlation, the pattern should be the gray-level pattern. In this paper, we discuss how to use discrete quaternion correlation (DQCR) for the application of color pattern recognition. With the algorithm introduced here, we can detect the objects that have the same shape, color, and brightness as the reference pattern. Besides, we can also detect (a) the objects with the same shape, color, but different brightness, (b) the objects with the same shape, brightness, but different color, and (c) the objects just have the same shape as the reference. Our algorithm can classify the objects into 5 classes due to whether their shape, brightness, and color match those of the reference pattern. Besides, with our algorithm, the difference of the brightness and color can also be calculated at the same time.