In the game of KAYLES, two players select alternatingly a vertex from a given graph G, but may never choose a vertex that is adjacent or equal to an already chosen vertex. The last player that can select a vertex wins...
详细信息
In the game of KAYLES, two players select alternatingly a vertex from a given graph G, but may never choose a vertex that is adjacent or equal to an already chosen vertex. The last player that can select a vertex wins the game. In this paper, we give an exact algorithm to determine which player has a winning strategy in this game. To analyze the running time of the algorithm, we introduce the notion of a K-set: a nonempty set of vertices W subset of V is a K-set in a graph G = (V, E), if G[W] is connected and there exists an independent set X such that W = V - N[X]. The running time of the algorithm is bounded by a polynomial factor times the number of K-sets in G. We prove that the number of K-sets in a graph with n vertices is bounded by O(1.6052(n)). A computer-generated case analysis improves this bound to O(1.6031(n)) K-sets, and thus we have an upper bound of O(1.6031(n)) on the running time of the algorithm for KAYLES. We also show that the number of K-sets in a tree is bounded by n center dot 3(n/3) and thus KAYLEs can be solved on trees in O(1.4423(n)) time. We show that apart from a polynomial factor, the number of K-sets in a tree is sharp. As corollaries, we obtain that determining which player has a winning strategy in the games G(avoid)(POSDNF2) and G(seek)(POSDNF3) can also be determined in O(1.6031(n)) time. In G(avoid)(POSDNF2), we have a positive formula F on n Boolean variables in Disjunctive Normal Form with two variables per clause. Initially, all variables are false, and players alternately set a variable from false to true;the first player that makes F true loses the game. The game G(seek)(POSDNF3) is similar, but now there are three variables per clause, and the first player that makes F true wins the game. (C) 2014 Elsevier B.V. All rights reserved.
Given a symmetric D x D matrix M over {0, 1, *}, a list M-partition of a graph G is a partition of the vertices of G into D parts which are associated with the rows of M. The part of each vertex is chosen from a given...
详细信息
Given a symmetric D x D matrix M over {0, 1, *}, a list M-partition of a graph G is a partition of the vertices of G into D parts which are associated with the rows of M. The part of each vertex is chosen from a given list in such a way that no edge of G is mapped to a 0 in M and no nonedge of G is mapped to a 1 in M. Many important graph-theoretic structures can be represented as list M-partitions including graph colorings, split graphs, and homogeneous sets and pairs, which arise in the proofs of the weak and strong perfect graph conjectures. Thus, there has been quite a bit of work on determining for which matrices M computations involving list M-partitions are tractable. This paper focuses on the problem of counting list M-partitions, given a graph G and given a list for each vertex of G. We identify a certain set of "tractable" matrices M. We give an algorithm that counts list M-partitions in polynomial time for every (fixed) matrix M in this set. The algorithm relies on data structures such as sparse-dense partitions and subcube decompositions to reduce each problem instance to a sequence of problem instances in which the lists have a certain useful structure that restricts access to portions of M in which the interactions of 0s and 1s are controlled. We show how to solve the resulting restricted instances by converting them into particular counting constraint satisfaction problems (#CSPs), which we show how to solve using a constraint satisfaction technique known as arc-consistency. For every matrix M for which our algorithm fails, we show that the problem of counting list M-partitions is #P-complete. Furthermore, we give an explicit characterization of the dichotomy theorem: counting list M-partitions is tractable (in FP) if the matrix M has a structure called a derectangularizing sequence. If M has no derectangularizing sequence, we show that counting list M-partitions is #P-hard. We show that the metaproblem of determining whether a given matrix has a dere
graph spanners are sparse subgraphs that preserve the distances of the original graph up to some approximation ratio (the spanner's stretch). A number of algorithms are known for constructing sparse spanners with ...
详细信息
graph spanners are sparse subgraphs that preserve the distances of the original graph up to some approximation ratio (the spanner's stretch). A number of algorithms are known for constructing sparse spanners with small multiplicative or additive stretch. Recently, algorithms were introduced for constructing fault-tolerant multiplicative spanners of general graphs. This paper addresses the analogous problem of constructing fault tolerant additive and (mu, alpha)-spanners for general graphs, and presents a number of (deterministic and randomized) construction algorithms for such spanners. (C) 2015 Elsevier B.V. All rights reserved.
We present techniques to improve convergence speed of distributed average consensus algorithms in wireless sensor networks by means of topology design. A broadcast network is assumed, so that only the transmit power o...
详细信息
We present techniques to improve convergence speed of distributed average consensus algorithms in wireless sensor networks by means of topology design. A broadcast network is assumed, so that only the transmit power of each node can be independently controlled, rather than each individual link. Starting with a maximally connected configuration in which all nodes transmit at full power, the proposed methods successively reduce the transmit power of a chosen node in order to remove one and only one link;nodes are greedily selected either in order to yield fastest convergence at each step, or if they have the largest degree in the network. These greedy schemes provide a good complexity-performance tradeoff with respect to full-blown global search methods. As a side benefit, improving the convergence speed also results in savings in energy consumption with respect to the maximally connected setting. (C) 2014 Elsevier B.V. All rights reserved.
The Maximal Independent Set (MIS) problem is one of the basics in the study of locality in distributed graph algorithms. This paper presents a very simple randomized algorithm for this problem providing a near-optimal...
详细信息
ISBN:
(纸本)9781510819672
The Maximal Independent Set (MIS) problem is one of the basics in the study of locality in distributed graph algorithms. This paper presents a very simple randomized algorithm for this problem providing a near-optimal local complexity, which incidentally, when combined with some known techniques, also leads to a near-optimal global complexity. Classical MIS algorithms of Luby [STOC'85] and Alon, Babai and Itai [JALG'86] provide the global complexity guarantee that, with high probability, all nodes terminate after O(log n) rounds. In contrast, our initial focus is on the local complexity, and our main contribution is to provide a very simple algorithm guaranteeing that each particular node v terminates after O(log deg(v) + log 1/ε) rounds, with probability at least 1 - ε. The degree-dependency in this bound is optimal, due to a lower bound of Kuhn, Moscibroda, and Wattenhofer [PODC'04]. Interestingly, this local complexity smoothly transitions to a global complexity: by adding techniques of Barenboim, Elkin, Pettie, and Schneider [FOCS'12; arXiv: 1202.1983v3], we get an MIS algorithm with a high probability global complexity of O(logΔ) + 2~(O({the square root of}(log log n))), where Δ denotes the maximum degree. This improves over the O(log~2 Δ) + 2_(O({the square root of}(log log n))) result of Barenboim et al., and gets close to the Ω(min{log Δ, {the square root of}(log n)}) lower bound of Kuhn et al. Corollaries include improved algorithms for MIS in graphs of upper-bounded arboricity, or lower-bounded girth, for Ruling Sets, for MIS in the Local Computation algorithms (LCA) model, and a faster distributed algorithm for the Lovasz Local Lemma.
Given a complete edge-weighted graph G, we present a polynomial time algorithm to. compute a degree-four-bounded spanning Eulerian subgraph of 2G that has at most 1.5 times the weight of an optimal TSP solution of G. ...
详细信息
Given a complete edge-weighted graph G, we present a polynomial time algorithm to. compute a degree-four-bounded spanning Eulerian subgraph of 2G that has at most 1.5 times the weight of an optimal TSP solution of G. Based on this algorithm and a novel use of orientations, in graphs, we obtain a (3 beta/4 + 3 beta(2)/4)-approximation algorithm for TSP with beta-relaxed triangle inequality (beta-TSP), where beta >= 1. A graph G is an insfance of beta-TSP, if it is a complete graph with edge weights c: E(G) -> Q >= 0 that are restricted as follows. For each triple of vertices u, v, w is an element of V (G), c({u, v}) <= beta(c({u, w}) + c ({w, v})). (C) 2015 Elsevier B.V. All rights reserved.
A subset L subset of V of a graph G = (V, E) is called a liar's dominating set of G if (i) vertical bar N-G[u] boolean AND L vertical bar >= 2 for every vertex u is an element of V, and (ii) vertical bar N-G [u...
详细信息
A subset L subset of V of a graph G = (V, E) is called a liar's dominating set of G if (i) vertical bar N-G[u] boolean AND L vertical bar >= 2 for every vertex u is an element of V, and (ii) vertical bar N-G [u] boolean OR N-G[v]) boolean AND L vertical bar >= 3 for every pair of distinct vertices u, v is an element of V. The MIN LIAR Dom SET problem is to find a liar's dominating set of minimum cardinality of a given graph G and the DECIDE LIAR Dom SET problem is the decision version of the MIN LIAR Dom SET problem. The DECIDE LIAR DOM SET problem is known to be NP-complete for general graphs. In this paper, we first present approximation algorithms and hardness of approximation results of the MIN LIAR Dom SET problem in general graphs, bounded degree graphs, and p-claw free graphs. We then show that the DECIDE LIAR Dom SET problem is NP-complete for doubly chordal graphs and propose a linear time algorithm for computing a minimum liar's dominating set in block graphs. (C) 2015 Elsevier B.V. All rights reserved.
A coloring of a digraph with non-negative edge weights is a partition of the vertex set into independent sets, where a set is independent if the weighted in-degree of each node within the set is less than 1. We give c...
详细信息
A coloring of a digraph with non-negative edge weights is a partition of the vertex set into independent sets, where a set is independent if the weighted in-degree of each node within the set is less than 1. We give constructive optimal bounds on the chromatic number in terms of maximum in-degree and inductiveness of the graph. (C) 2015 Elsevier B.V. All rights reserved.
Given a graph G, a spanning subgraph H of G and an integer lambda >= 2, a lambda-backbone coloring of G with backbone H is a proper vertex coloring of G using colors 1,2,..., in which the color difference between v...
详细信息
Given a graph G, a spanning subgraph H of G and an integer lambda >= 2, a lambda-backbone coloring of G with backbone H is a proper vertex coloring of G using colors 1,2,..., in which the color difference between vertices adjacent in H is greater than or equal to lambda. The backbone coloring problem is that of finding such a coloring whose maximum color does not exceed a given limit k. In this paper, we study the backbone coloring problem for bounded-degree graphs with connected backbones and we give a complete computational complexity classification of this problem. We present a polynomial algorithm for optimal backbone coloring for subcubic graphs with arbitrary backbones. We also prove that the backbone coloring problem for graphs with arbitrary backbones and with fixed maximum degree (at least 4) is NP-complete. Furthermore, we show that for the special case of graphs with fixed maximum degree at least 5 and lambda >= 4 the problem remains NP-complete even for spanning tree backbones. (C) 2014 Elsevier B.V. All rights reserved.
Reducing the energy consumed by wired computer networks is a challenge that has been actively investigated over the past few years. A popular mechanism proposed to reduce the consumption aims to put links and line car...
详细信息
ISBN:
(纸本)9781479966653
Reducing the energy consumed by wired computer networks is a challenge that has been actively investigated over the past few years. A popular mechanism proposed to reduce the consumption aims to put links and line cards to sleep mode during off-peak hours. Such a mechanism, however, decreases the available network capacity and increases the risk of congestion if traffic rises unexpectedly. This paper proposes a solution to rapidly react to network bursts and turn-on sleeping links, which we term as SegmenT Routing based Energy Efficient Traffic Engineering for switching ON (STREETE-ON). The proposed algorithm was implemented in the OMNeT++ network simulator using state-of-art dynamic graph algorithms. In such a way, we achieved execution times of tens of milliseconds for a 50-node network. Experimental results show that STREETE-ON can effectively prevent network congestion, avoid turning-on unneeded links, and preserve good energy-efficiency of the network.
暂无评论