6381363
Weighted Domination of Cocomparability Graphs
It is shown in this paper that the weighted domination problem and its two variants, the weighted connected domination and weighted total domination problems are NP-complete on cocomparability graphs when arbitrary integer vertex weights are allowed and all of them can be solved in polynomial time if vertex weights are integers and less than or equal to a constant c. Besides, an O(¦V¦2) algorithm is given for the weighted independent perfect domination problem of a cocomparability graph G=(V, E).
36993971
Distance-hereditary graphs are clique-perfect
In this paper, we show that the clique-transversal number @t"C(G) and the clique-independence number @a"C(G) are equal for any distance-hereditary graph G. As a byproduct of proving that @t"C(G)[email protected]"C(G), we give a linear-time algorithm to find a minimum clique-transversal set and a maximum clique-independent set simultaneously for distance-hereditary graphs.
205343201
Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs,
A Hamiltonian path of a graph G is a simple path that contains each vertex of G exactly once. A Hamiltonian cycle of a graph is a simple cycle with the same property. The Hamiltonian path (resp. cycle) problem involves testing whether a Hamiltonian path (resp. cycle) exists in a graph. The 1HP (resp. 2HP) problem is to determine whether a graph has a Hamiltonian path starting from a specified vertex (resp. starting from a specified vertex and ending at the other specified vertex). The Hamiltonian problems include the Hamiltonian path, Hamiltonian cycle, 1HP, and 2HP problems. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. In this paper, we present a unified approach to solving the Hamiltonian problems on distance-hereditary graphs in linear time.
207137932
On-Line Chinese Character Recognition by Incorporating Human Knowledge
A stroke order and number free method for on-line recognition of Chinese characters is proposed. Both input characters and the model characters are represented with complete attributed relational graphs (ARGs). The ARGs of the model base are built according to the human knowledge of the segment relation structure of Chinese characters. For the recognition purpose, an optimal matching measure between two ARGs is defined, and the graph matching is formulated as a search problem of finding the minimum cost path in a state space tree, using the A* algorithm. Moreover, to reduce the search time of the A*, besides a heuristic estimate, a novel strategy is employed which again uses the human knowledge of the segment position structure of Chinese characters to prune the tree. Our experimental results demonstrate the efficiency of the proposed method.
10053237
Automated least-significant bit datapath optimization for FPGAs
In this paper, we present a method for FPGA datapath precision optimization subject to user-defined area and error constraints. This work builds upon our previous research which presented a methodology for optimizing the dynamic range- the most significant bit position. In this work, we present an automated optimization technique for the least-significant bit position of circuit datapaths. We present results describing the effectiveness of our methods on typical signal and image processing kernels.
466097
Merging artificial objects with marker-less video sequences based on the interacting multiple model method
Inserting synthetic objects into video sequences has gained much interest in recent years. Fast and robust vision-based algorithms are necessary to make such an application possible. Traditional pose tracking schemes using recursive structure from motion techniques adopt one Kalman filter and thus only favor a certain type of camera motion. We propose a robust simultaneous pose tracking and structure recovery algorithm using the interacting multiple model (IMM) to improve performance. In particular, a set of three extended Kalman filters (EKFs), each describing a frequently occurring camera motion in real situations (general, pure translation, pure rotation), is applied within the IMM framework to track the pose of a scene. Another set of EKFs,one filter for each model point, is used to refine the positions of the model features in the 3-D space. The filters for pose tracking and structure refinement are executed in an interleaved manner. The results are used for inserting virtual objects into the original video footage. The performance of the algorithm is demonstrated with both synthetic and real data. Comparisons with different approaches have been performed and show that our method is more efficient and accurate.
16598523
Algorithmic Aspects of the Generalized Clique-transversal Problem on Chordal Graphs
Suppose G = (V, E) is a graph in which each maximal clique Ci is associated with an integer ri, where 0 ⩽ ri ⩽ ¦Ci¦. The generalized clique transversal problem is to determine the minimum cardinality of a subset D of V such that ¦D ∩ Ci¦ ⩾ ri for every maximal clique Ci 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.
11770804
Measuring dynamic memory invocations in object-oriented programs
Dynamic memory management has been a high cost component in many software systems. Studies have shown that memory intensive C programs can consume up to 30% of the program runtime in memory allocation and liberation. The OOP language system tends to perform object creation and deletion prolifically. An empirical study shown that C++ programs can have ten times more memory allocation and deallocation than comparable C programs. However, the allocation behavior of C++ programs is rarely reported. This paper attempts to locate where the dynamic memory allocations are coming from and report an empirical study of dynamic memory invocations in C++ programs. Firstly, this paper summarizes the hypothesis of situations that invoke the dynamic memory management explicitly and implicitly. They are: constructors, copy constructors, overloading assignment operator=, type conversions and application specific member functions. Secondly, the development of a source code level tracing tool is reported as the procedure to investigate the hypothesis. Thirdly, results include behavioral patterns of memory allocations. With these patterns, we may increase the reusability of the resources. For example, a profile-based strategy can be used to improve the performance of dynamic memory management. The C++ programs that were traced include Java compiler, CORBA compliant and visual framework.