26237409
On Minimum Intersection of Two Minimum Dominating Sets of Interval Graphs
This paper gives linear-time algorithms for finding two minimum (connected) dominating sets with minimum intersection for interval 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.
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.
9894533
20-Relative Neighborhood Graphs Are Hamiltonian
670153
Domination in distance-hereditary graphs
The domination problem and its variants have been extensively studied in the literature. In this paper we investigate the domination problem in distance-hereditary graphs. In particular, we give a linear-time algorithm for the domination problem in distance-hereditary graphs by a labeling approach. We actually solve a more general problem, called the L-domination problem, which also includes the total domination problem as a special case.
16824799
A heuristic method for self‐healing ring design in a single‐homing cluster
In this paper, we consider a SONET (Synchronous Optical NETwork) USHR (Uni‐directional Self‐Healing Ring) design problem for a single‐homing cluster, i.e., a cluster with a single designated hub. The problem is formulated as a nonlinear integer programming problem and a branch and bound heuristic method based on the Lagrangian relaxation and subgradient optimization technique is proposed to handle the problem. In solving any ring design problem, we should deal with two different aspects of the ring design, namely, the ring routing aspect and the ring loading aspect. Both of these two aspects are well integrated and represented in our model. Such an integrated formulation has not been proposed in the existing literature mainly due to its computationally intractable complexity. In order to cope with such complexity, a preprocessing technique for reducing the complexity and several branch and bound strategies are proposed. The efficiency of the proposed method is tested through computational experiments. For the computational experiments, test problems are generated using the data obtained from the actual topologies in Seoul, Korea. The computational experiments show that the proposed method yields near‐optimum designs within reasonable computation time.
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.
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.