Experimental Analysis of Heuristic Algorithms for the Dominating Set Problem

We say a vertex v in a graph G covers a vertex w if v=w or if v and w are adjacent. A subset of vertices of G is a dominating set if it collectively covers all vertices in the graph. The dominating set problem, which is NP-hard, consists of finding a smallest possible dominating set for a graph. The straightforward greedy strategy for finding a small dominating set in a graph consists of successively choosing vertices which cover the largest possible number of previously uncovered vertices. Several variations on this greedy heuristic are described and the results of extensive testing of these variations is presented. A more sophisticated procedure for choosing vertices, which takes into account the number of ways in which an uncovered vertex may be covered, appears to be the most successful of the algorithms which are analyzed. For our experimental testing, we used both random graphs and graphs constructed by test case generators which produce graphs with a given density and a specified size for the smallest dominating set. We found that these generators were able to produce challenging graphs for the algorithms, thus helping to discriminate among them, and allowing a greater variety of graphs to be used in the experiments. Received October 27, 1998; revised March 25, 2001.     

Stochastic Local Search Algorithms for Graph Set <Emphasis Type="Italic">T</Emphasis>-colouring and Frequency Assignment

The graph set T-colouring problem (GSTCP) generalises the classical graph colouring problem; it asks for the assignment of sets of integers to the vertices of a graph such that constraints on the separation of any two numbers assigned to a single vertex or to adjacent vertices are satisfied and some objective function is optimised. Among the objective functions of interest is the minimisation of the difference between the largest and the smallest integers used (the span). In this article, we present an experimental study of local search algorithms for solving general and large size instances of the GSTCP. We compare the performance of previously known as well as new algorithms covering both simple construction heuristics and elaborated stochastic local search algorithms. We investigate systematically different models and search strategies in the algorithms and determine the best choices for different types of instance. The study is an example of design of effective local search for constraint optimisation problems.     

A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graph

We show that anyk-connected graphG = (V, E) has a sparsek-connected spanning subgraphG = (V, E) with ¦E¦ =O(k¦V¦) by presenting anO(¦E¦)-time algorithm to find one such subgraph, where connectivity stands for either edge-connectivity or node-connectivity. By using this algorithm as preprocessing, the time complexities of some graph problems related to connectivity can be improved. For example, the current best time boundO(max{k ²¦V¦^1/2,k¦V¦}¦E¦) to determine whether node-connectivityK(G) of a graphG = (V, E) is larger than a given integerk or not can be reduced toO(max{k ³¦V¦^3/2,k ²¦V¦²}).The first author was partially supported by the Grant-in-Aid for Encouragement of Young Scientists of the Ministry of Education, Science and Culture of Japan and by the subvention to young scientists by the Research Foundation of Electrotechnology of Chubu.     

Structural properties of minimax controllers for a class of differential games arising in nonlinear H control

This paper introduces, in precise mathematical terms, two properties (named, certainty equivalence and generalized certainty equivalence) that nonlinear minimax controller problems might possess. The certainty equivalence is a generalization of the one introduced earlier by Ba ar and Bernhard (1991) and Bernhard (1990), which applies to problems where the ‘worst-case disturbance’ may not be unique (but the worst-case state trajectory is). The generalized certainty equivalance, on the other hand, extends this to accomodate nonunique worst-case state trajectories, and leads to the constrollers that guarantee a bounded upper value for the underlying game. The paper also shows that for a large class of games (and under certain conditions), certainty-equivalent (as well as generalized certainty-equivalent) controllers admit (infinite-dimensional) estimator (Kalman-filter) structures, where the estimator gain depends on the state of the estimator.     

New applications of clique separator decomposition for the Maximum Weight Stable Set problem

Graph decompositions such as decomposition by clique separators and modular decomposition are of crucial importance for designing efficient graph algorithms. Clique separators in graphs were used by Tarjan as a divide-and-conquer approach for solving various problems such as the Maximum Weight Stable Set (MWS) problem, Colouring and Minimum Fill-in. The basic tool is a decomposition tree of the graph whose leaves have no clique separator (so-called atoms), and the problem can be solved efficiently on the graph if it is efficiently solvable on its atoms. We give new examples where the clique separator decomposition works well for the MWS problem; our results improve and extend various recently published results. In particular, we describe the atom structure for some new classes of graphs whose atoms are P₅-free (the P₅ is the induced path with five vertices) and obtain new polynomial time results for the MWS problem. The complexity of this problem on the class of P₅-free graphs is still unknown.