Dominating sets in directed graphs

We consider the problem of incrementally computing a minimal dominating set of a directed graph after the insertion or deletion of a set of arcs. Earlier results have either focused on the study of the properties that minimum (not minimal) dominating sets preserved or lacked to investigate which update affects a minimal dominating set and in what ways. In this paper, we first show how to incrementally compute a minimal dominating set on arc insertions. We then reduce the case of computing a minimal dominating set on arc deletions to the case of insertions. Some properties on minimal dominating sets are provided to support the incremental strategy. Lastly, we give a new bound on the size of minimum dominating sets based on those results.     

Energy Efficient Monitoring in Sensor Networks

We study a set of problems related to efficient battery energy utilization for monitoring applications in a wireless sensor network with the goal to increase the sensor network lifetime. We study several generalizations of a basic problem called Set k-Cover. The problem can be described as follows: we are given a set of sensors, and a set of targets to be monitored. Each target can be monitored by a subset of the sensors. To increase the lifetime of the sensor network, we would like to partition the sensors into k sets (or time-slots), and activate each set of sensors in a different time-slot, thus extending the battery life of the sensors by a factor of k. The goal is to find a partitioning that maximizes the total coverage of the targets for a given k. This problem is known to be NP-hard. We develop an improved approximation algorithm for this problem using a reduction to Max k-Cut. Moreover, we are able to demonstrate that this algorithm is efficient, and yields almost optimal solutions in practice.     

Stability in L systems

Given an L System G, a word w is said to be k-stable in G if, once w occurs in a derivation, the derivation can proceed no more than k steps before the next occurence of w. The set of k-stable words in an L System is called the k-stable language of the system. The k-stable languages of the main classes of L Systems are characterized by the Adult languages of the corresponding classes. This work provides a new characterization of the Chomsky hierarchy in terms of totally parallel grammars, and some consequences of this characterization are explored.     

Partitioning trees: Matching,domination, and maximum diameter

A matching and a dominating set in a graph G are related in that they determine diameter-bounded subtree partitions of G. For a maximum matching and a minimum dominating set, the associate partitions have the fewest numbers of trees. The problem of determining a minimum dominating set in an arbitrary graph G is known to be NP-complete. In this paper we present a linear algorithm for partitioning an arbitrary tree into a minimum number of subtrees, each having a diameter at mostk, for a givenk.Research supported in part by the National Science Foundation under Grant ENG 7902960.Research supported in part by the National Science Foundation under Grant STI 7902960.     

Threshold-based probabilistic top-k dominating queries

Recently, due to intrinsic characteristics in many underlying data sets, a number of probabilistic queries on uncertain data have been investigated. Top-k dominating queries are very important in many applications including decision making in a multidimensional space. In this paper, we study the problem of efficiently computing top-k dominating queries on uncertain data. We first formally define the problem. Then, we develop an efficient, threshold-based algorithm to compute the exact solution. To overcome some inherent computational deficiency in an exact computation, we develop an efficient randomized algorithm with an accuracy guarantee. Our extensive experiments demonstrate that both algorithms are quite efficient, while the randomized algorithm is quite scalable against data set sizes, object areas, k values, etc. The randomized algorithm is also highly accurate in practice.     

Complexity of computing with extended propositional logic programs

In this paper we introduce the notion of anF-program, whereF is a collection of formulas. We then study the complexity of computing withF-programs.F-programs can be regarded as a generalization of standard logic programs. Clauses (or rules) ofF-programs are built of formulas fromF. In particular, formulas other than atoms are allowed as building blocks ofF-program rules. Typical examples ofF are the set of all atoms (in which case the class of ordinary logic programs is obtained), the set of all literals (in this case, we get the class of logic programs with classical negation [9]), the set of all Horn clauses, the set of all clauses, the set of all clauses with at most two literals, the set of all clauses with at least three literals, etc. The notions of minimal and stable models [16, 1, 7] of a logic program have natural generalizations to the case ofF-programs. The resulting notions are called in this paperminimal andstable answer sets. We study the complexity of reasoning involving these notions. In particular, we establish the complexity of determining the existence of a stable answer set, and the complexity of determining the membership of a formula in some (or all) stable answer sets. We study the complexity of the existence of minimal answer sets, and that of determining the membership of a formula in all minimal answer sets. We also list several open problems.This work was partially supported by National Science Foundation under grant IRI-9012902.This work was partially supported by National Science Foundation under grant CCR-9110721.     

Threshold Utility, Choice, and Binary Relations

Representation of the binary relations and choice functions by the utility functions was considered. The results of utility maximization were presented for the classical case of no comparison threshold and with a threshold depending on one alternative. Models were constructed where the threshold depends on two compared alternatives and/or admissible set of alternatives. A model of choice describing H.A. Simon's concept of choice was proposed and considered. The class of binary relations of partial order and its subclasses were studied. Some new classes of binary relations such as weak biorders and simple and simplest semiorders were constructed, and their representations by the threshold utility function were determined.     

A simple group mutual l-exclusion algorithm

This work deals with the domination numbers of generalized de Bruijn digraphs and generalized Kautz digraphs. Dominating sets for digraphs are not familiar compared with dominating sets for undirected graphs. Whereas dominating sets for digraphs have more applications than those for undirected graphs. We construct dominating sets of generalized de Bruijn digraphs where obtained dominating sets have some qualifications. For generalized Kautz digraphs, there is a minimum dominating set in those constructed dominating sets.     

无线传感器网络中2-连通k-支配的容错连通支配集构造

无线传感器网络可采用连通支配集的虚拟骨干技术使平面网络层次化,但传感器节点的失效和链路的断裂会导致网络失败,虚拟骨干网最好具有容错性好、可靠性高的特性.对此,提出具有容错性的2-连通 -支配集的构造算法,以节点自身和邻域信息分布式地构造 -支配节点,利用最小生成树和块-割点图将 -支配节点2-连通.理论分析和实验仿真表明此算法具有较好的算法性能比,在中等规模网络中会产生更少的具有容错性的 -支配节点,可节省传感器节点的能量消耗和网络的通信开销.     

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.     

Rating and ranking of multiple-aspect alternatives using fuzzy sets

A method is proposed to deal with multiple-alternative decision problems under uncertainty. It is assumed that all the alternatives in the choice set can be characterized by a number of aspects, and that information is available to assign weights to these aspects and to construct a rating scheme for the various aspects of each alternative. The method basically consists of computing weighted final ratings for each alternative and comparing the weighted final ratings. The uncertainty that is assumed to be inherent in the assessments of the ratings and weights is accounted for by considering each of these variables as fuzzy quantities, characterized by appropriate membership functions. Accordingly, the final evaluation of the alternatives consists of a degree of membership in the fuzzy set of alternatives ranking first. A practical method is given to compute membership functions of fuzzy sets induced by mappings, and applied to the problem at hand. A number of examples are worked out. The method is compared to another one proposed by Kahne who approaches the problem probabilistically.     

On the size of randomized OBDDs and read-once branching programs for k-stable functions

In this paper, a simple technique which unifies the known approaches for proving lower bound results on the size of deterministic, nondeterministic, and randomized OBDDs and kOBDDs is described.?As an application of this technique, a generic lower bound on the size of randomized OBDDs with bounded error is established for a class of functions which has been studied in the literature on branching programs for a long time. These functions have been called “k-stable” by Jukna. It follows that several standard functions are not contained in the analog of the class BPP for OBDDs. Furthermore, exponential lower bounds on the size of randomized kOBDDs are presented.?It is well known that k-stable functions with large k are hard for deterministic read-once branching programs. This is no longer true in the randomized case. It is shown here that a certain k-stable function due to Jukna, Razborov, Savicky, and Wegener has randomized branching programs of polynomial size, even with zero error. It follows that for the analogs of these classes defined in terms of the size of read-once branching programs. Received: September 3, 1998.     

Productive functions and isomorphisms

Joseph and Young [5] conjectured that there are non-p-isomorphic NP-complete sets if ak-creative set in NP exists which has no p-invertible p-productive function. We prove that this conjecture is true for the exponential-time (deterministic and nondeterministic) complexity classes E and NE. In particular, we prove that non-p-isomorphic E-complete sets exist if and only if there is a p-creative set in E which has no p-invertible p-productive function. Similar result holds for NE as well.This work was supported in part by NSF Grants CCR-8814339 and CCR-9108899.     

Intelligent product search with soft-boundary preference relaxation

This paper proposes a novel method for preference relaxation in online product search, which enables consumers to make quality choices without suffering from the commonly experienced information overload. In online shopping scenarios that involve multi-attribute choice tasks, it can be difficult for consumers to process the vast amounts of information available and to make satisfactory buying decisions. In such situations consumers are likely to eliminate potentially good choices early on, using hard-constraint filtering tools. Our approach uses edge sets to identify the alternatives on the soft boundary and the principle of alternative domination to suppress the alternatives on this boundary that are irrelevant. We demonstrate how our approach outperforms existing methods for product search in a set of simulations using two sets of 2650 car advertisements and 1813 digital cameras gathered from a popular online store.     

无线网络中一种简单的弱连通支配集构造策略

通过构造边支配集,提出了求解无线网络中弱连通支配集的集中式构造算法,该算法的时间复杂度为O（|N|+|E|）。同时在保证支配集的支配性和弱连通性不变的情况下,给出了两种修剪策略,以减小所求弱连通支配集的规模。从理论上证明了本算法的正确性,并通过仿真验证了算法的有效性。与已有结果相比,该算法可以产生规模更小的弱连通支配集。     

Constructing minimum extended weakly-connected dominating sets for clustering in ad hoc networks

Motivated by cooperative communication in ad hoc networks, Wu et al. proposed extended dominating set (EDS) where each node in an ad hoc network is covered by either a dominating neighbor or several 2-hop dominating neighbors, and defined two types of dominating sets: extended strongly connected dominating set (ECDS) and extended weakly connected dominating set (EWCDS), according to the success of a broadcast process. An EWCDS is an effective method for clustering. In this paper, we extend the dominative capabilities of nodes such that each forward node dominates not only itself and its regular neighbors fully, but also its quasi-neighbors partly. Based on this extension, three novel algorithms to find EWCDSs in ad hoc networks are proposed. The correctness and performance of our algorithms are confirmed through theoretical analysis and comprehensive simulations.     

Optimal partitioning of groups in selecting the best choice

This article deals with the group interview problem, in which each group contains several alternatives and each group of alternatives is presented and evaluated sequentially over time. We derive the optimal selection strategy for the group interview problem with a general utility function. Among the various types of utility function, we focus on the best choice problem, in which our utility is one if we successfully select the best choice and zero otherwise. We derive a simple selection rule called the optimal partitioning strategy in which the decision-maker divides the entire groups into two disjoint sets and, after evaluating the choices in the first set, chooses the relatively best choice available for the first time in the second set. Because the selected choice is not necessarily the absolutely best choice, we also consider the probability distribution of the actual rank of the choice selected under the partitioning strategy.

Scope and purpose

In many managerial decision situations such as buying a car, selling a house, or searching for a job, several alternatives are presented sequentially and an accept-or-reject decision is made immediately after evaluating each alternative. The classical secretary problem and its extensions have been successfully applied to such a sequential search and selection problem. This article deals with a more generalized version of the secretary problem, called the group interview problem, in which several groups of alternatives are presented and evaluated sequentially over time. Based on a stochastic dynamic programming approach, we propose the optimal selection strategy for the group interview problem with various types of the decision-maker's utility function. There are many potential applications of the group interview problem, including consumer search and purchase process, job search problem, sequential assignment of batch jobs, and so on.     

Parallel algorithms for separation of two sets of points and recognition of digital convex polygons

Given two finite sets of points in a plane, the polygon separation problem is to construct a separating convexk-gon with smallestk. In this paper, we present a parallel algorithm for the polygon separation problem. The algorithm runs inO(logn) time on a CREW PRAM withn processors, wheren is the number of points in the two given sets. The algorithm is cost-optimal, since (n logn) is a lower-bound for the time needed by any sequential algorithm. We apply this algorithm to the problem of finding a convex polygon, with the minimal number of edges, for which a given convex region is its digital image. The algorithm in this paper constructs one such polygon with possibly two more edges than the minimal one.The research is sponsored by NSERC Operating Grant OGPIN 007.     

Multicategory Proximal Support Vector Machine Classifiers

Given a dataset, each element of which labeled by one of k labels, we construct by a very fast algorithm, a k-category proximal support vector machine (PSVM) classifier. Proximal support vector machines and related approaches (Fung & Mangasarian, 2001; Suykens & Vandewalle, 1999) can be interpreted as ridge regression applied to classification problems (Evgeniou, Pontil, & Poggio, 2000). Extensive computational results have shown the effectiveness of PSVM for two-class classification problems where the separating plane is constructed in time that can be as little as two orders of magnitude shorter than that of conventional support vector machines. When PSVM is applied to problems with more than two classes, the well known one-from-the-rest approach is a natural choice in order to take advantage of its fast performance. However, there is a drawback associated with this one-from-the-rest approach. The resulting two-class problems are often very unbalanced, leading in some cases to poor performance. We propose balancing the k classes and a novel Newton refinement modification to PSVM in order to deal with this problem. Computational results indicate that these two modifications preserve the speed of PSVM while often leading to significant test set improvement over a plain PSVM one-from-the-rest application. The modified approach is considerably faster than other one-from-the-rest methods that use conventional SVM formulations, while still giving comparable test set correctness.Editor Shai Ben-David