On the All-Farthest-Segments problem for a planar set of points

In this note, we outline a very simple algorithm for the following problem: Given a set S of n points p₁,p₂,p₃,…,pn in the plane, we have O(n²) segments implicitly defined on pairs of these n points. For each point pi, find a segment from this set of implicitly defined segments that is farthest from pi. The time complexity of our algorithm is in O(nh+nlogn), where n is the number of input points, and h is the number of vertices on the convex hull of S.     

A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs

In recent years growing interest in local distributed algorithms has widely been observed. This results from their high resistance to errors and damage, as well as from their good performance, which is independent of the size of the network. A local deterministic distributed algorithm finding an approximation of a Minimum Dominating Set in planar graphs has been presented by Lenzen et al., and they proved that the algorithm returns a 130-approximation of the Minimum Dominating Set. In this article we will show that the algorithm is two times more effective than was previously assumed, and we prove that the algorithm by Lenzen et al. outputs a 52-approximation to a Minimum Dominating Set. Therefore the gap between the lower bound and the approximation ratio of the best yet local deterministic distributed algorithm is reduced by half.     

Finding a dominating set on bipartite graphs

Finding a dominating set of minimum cardinality is an NP-hard graph problem, even when the graph is bipartite. In this paper we are interested in solving the problem on graphs having a large independent set. Given a graph G with an independent set of size z, we show that the problem can be solved in time O^∗(²n−z), where n is the number of vertices of G. As a consequence, our algorithm is able to solve the dominating set problem on bipartite graphs in time O^∗(²n/2). Another implication is an algorithm for general graphs whose running time is O(n^1.7088).     

Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems

In the Hitting Set problem, we are given a collection F of subsets of a ground set V and an integer p, and asked whether V has a p-element subset that intersects each set in F. We consider two parameterizations of Hitting Set below tight upper bounds, p=m−k and p=n−k. In both cases k is the parameter. We prove that the first parameterization is fixed-parameter tractable, but has no polynomial kernel unless coNP ⊆ NP/poly. The second parameterization is W[1]-complete, but the introduction of an additional parameter, the degeneracy of the hypergraph H=(V,F), makes the problem not only fixed-parameter tractable, but also one with a linear kernel. Here the degeneracy of H=(V,F) is the minimum integer d such that for each X⊂V the hypergraph with vertex set V?X and edge set containing all edges of F without vertices in X, has a vertex of degree at most d.In Nonblocker (Directed Nonblocker), we are given an undirected graph (a directed graph) G on n vertices and an integer k, and asked whether G has a set X of n−k vertices such that for each vertex y∉X there is an edge (arc) from a vertex in X to y. Nonblocker can be viewed as a special case of Directed Nonblocker (replace an undirected graph by a symmetric digraph). Dehne et al. (Proc. SOFSEM 2006) proved that Nonblocker has a linear-order kernel. We obtain a linear-order kernel for Directed Nonblocker.     

On the fixed-parameter tractability of parameterized model-checking problems

In this note, we show, through the use of examples, how generic results for proving fixed-parameter tractability which apply to restricted classes of structures can sometimes be more widely applied.     

Parameterized approximation of dominating set problems

A problem open for many years is whether there is an FPT algorithm that given a graph G and parameter k, either: (1) determines that G has no k-Dominating Set, or (2) produces a dominating set of size at most g(k), where g(k) is some fixed function of k. Such an outcome is termed an FPT approximation algorithm. We describe some results that begin to provide some answers. We show that there is no such FPT algorithm for g(k) of the form k+c (where c is a fixed constant, termed an additive FPT approximation), unless FPT=W[2]. We answer the analogous problem completely for the related Independent Dominating Set (IDS) problem, showing that IDS does not admit an FPT approximation algorithm, for any g(k), unless FPT=W[2].     

有向图连通支配集求解算法

定义了有向图指定源点连通支配集问题。借助参数算法中的技术设计了针对该问题的规约规则,通过规约规则的实施来降低原问题的规模;随后又设计了近似算法在规约后的有向图中求出一个较小的连通支配集;最后结合规约规则带来的一些良好特性设计了优化规则,通过优化变换的实施进一步缩减由近似算法求得的连通支配集。不同模型随机图上的模拟实验表明这些规则和算法是有效的。     

Constant ratio fixed-parameter approximation of the edge multicut problem

The input of the Edge Multicut problem consists of an undirected graph G and pairs of terminals {s₁,t₁},…,{sm,tm}; the task is to remove a minimum set of edges such that si and ti are disconnected for every 1?i?m. The parameterized complexity of the problem, parameterized by the maximum number k of edges that are allowed to be removed, is currently open. The main result of the paper is a parameterized 2-approximation algorithm: in time f(k)⋅nO(1), we can either find a solution of size 2k or correctly conclude that there is no solution of size k.The proposed algorithm is based on a transformation of the Edge Multicut problem into a variant of the parameterized Max-2SAT problem, where the parameter is related to the number of clauses that are not satisfied. It follows from previous results that the latter problem can be 2-approximated in a fixed-parameter time; on the other hand, we show here that it is W[1]-hard. Thus the additional contribution of the present paper is introducing the first natural W[1]-hard problem that is constant-ratio fixed-parameter approximable.     

The fixed set search applied to the power dominating set problem

In this article, we focus on solving the power dominating set problem and its connected version. These problems are frequently used for finding optimal placements of phasor measurement units in power systems. We present an improved integer linear program (ILP) for both problems. In addition, a greedy constructive algorithm and a local search are developed. A greedy randomised adaptive search procedure (GRASP) algorithm is created to find near optimal solutions for large scale problem instances. The performance of the GRASP is further enhanced by extending it to the novel fixed set search (FSS) metaheuristic. Our computational results show that the proposed ILP has a significantly lower computational cost than existing ILPs for both versions of the problem. The proposed FSS algorithm manages to find all the optimal solutions that have been acquired using the ILP. In the last group of tests, it is shown that the FSS can significantly outperform the GRASP in both solution quality and computational cost.     

Computational complexity of queries based on itemsets

We investigate determining the exact bounds of the frequencies of conjunctions based on frequent sets. Our scenario is an important special case of some general probabilistic logic problems that are known to be intractable. We show that despite the limitations our problems are also intractable, namely, we show that checking whether the maximal consistent frequency of a query is larger than a given threshold is NP-complete and that evaluating the Maximum Entropy estimate of a query is PP-hard. We also prove that checking consistency is NP-complete.     

Fast algorithms for the dominating set problem on permutation graphs

AnO(n log logn) (resp.O(n² log² n)) algorithm is presented to solve the minimum cardinality (resp. weight) dominating set problem on permutation graphs, assuming the input is a permutation. The best-known previous algorithm was given by FÄrber and Keil, where they use dynamic programming to get anO(n² (resp.O(n³)) algorithm. Our improvement is based on the following three factors: (1) an observation on the order among the intermediate terms in the dynamic programming, (2) a new construction formula for the intermediate terms, and (3) efficient data structures for manipulating these terms.This research was supported in part by the National Science Foundation under Grant CCR-8905415 to Northwestern University.     

无向图中连通支配集问题的精确算法

图◢G=（V,E）的一个支配集DV是一个顶点子集,使得图中每一个顶点要么在D中,要么至少与D中的一个顶点相连。连通支配集问题是找到一个顶点数最小的支配集S,并且S的导出子图G［S］是连通图。◣该问题是一个经典的NP难问题,可应用于连通设施选址、自适应网络等领域。针对无向图中连通支配集问题,仔细分析该问题的图结构性质,挖掘出若干有效的约简规则和分支规则,设计了一个分支搜索算法,并采用了测量治之方法分析算法的运行时间,最终得到了一个运行时间复杂◢度为O*△（1.93n△）的精确◣算法。     

Computational modeling of city formation

Although a burst of recent research in economics has examined how industries form, a majority of it considers highly simplified models. In this paper, we use computational modeling techniques to expand from traditional, simple, analytically tractable economic models to more complex two dimensional landscapes. Using the basic theories developed in earlier research, we examine what factors cause cities to emerge, including: transportation costs, the percentage of workers in a population, and the elasticity of substitution. These three factors should cause workers and firms to agglomerate, causing cities to emerge out of a scattered population.     

Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler

This paper presents distributed self-stabilizing algorithms for the maximal independent and the minimal dominating set problems. Using an unfair distributed scheduler the algorithms stabilizes in at most max{3n−5,2n} resp. 9n moves. All previously known algorithms required O(n²) moves.     

A planar single-facility competitive location and design problem under the multi-deterministic choice rule

A new customer choice rule, which may model in some cases the actual patronising behaviour of customers towards the facilities closer to reality than other existing rules, is proposed. According to the new rule, customers split their demand among the firms in the market by patronising only one facility from each firm, the one with the highest utility, and the demand is split among those facilities proportionally to their attraction. The influence of the choice rule in the location of facilities is investigated. In particular, a new continuous competitive single-facility location and design problem using this new rule is proposed. Both exact and heuristic methods are proposed to solve it. A comparison with the classical proportional (or Huff) choice rule when solving the location model reveals that both the location and the quality of the new facility to be located may be quite different depending on the patronising behaviour of customers. Most importantly, the profit that the locating chain may lose if a wrong choice is made can be quite high in some instances.     

Ad hoc网络中基于权值的连通支配集算法

移动Ad hoe网络是一种多跳,自组织网络,在该网络中可以通过构建虚拟骨干网来减少参与路由计算的节点数量,虚拟骨干网可以由近似的最小连接主节点集(MCDS)组成.提出了一种考虑节点权值的分布式近似MCDS查找算法,在网络拓扑结构发生变化时对MCDS进行维护.与几种经典的分布式近似MCDS查找算法相比较,结果表明,该算法具有更好的性能.     

A two phase removing algorithm for minimum independent dominating set problem

The minimum independent dominating set (MIDS) problem is a famous combinatorial optimization problem and is widely used in real-world domains. In this paper, we design a novel local search algorithm with tabu method and two phase removing strategies including double-checked removing strategy and random diversity removing strategy to solve the MIDS problem. The first removing strategy checks and then removes the second-level neighbourhood of the just removal vertex to break the limitation of the independence property. When the quality of candidate solution has not been improved after some steps, the second removing strategy dynamically and greedily removes lots of vertices so that the current candidate solution can escape from suboptimal search space, and then we introduce the random walk into the repair process. Experiments are carried out on two classical benchmarks named DIMACS and BHOSLIB, and the results show that the proposed algorithm significantly outperforms the previous state-of-the-art MIDS heuristic algorithms.     

Maximum weight k-independent set problem on permutation graphs

Based on a Directed Acyclic Graph approach, an O(kn ²) time sequential algorithm is presented to solve the maximum weight k-independent set problem on weighted-permutation graphs. The weights considered here are all non-negative and associated with each of the n vertices of the graph. This problem has many applications in practical problems like k-machines job scheduling problem, k-colourable subgraph problem, VLSI design and routing problem.