检索结果-内蒙古大学图书馆

THEORETICAL COMPUTER SCIENCE 2015年第C期562卷 165-176页

作者： Bodlaender, Hans L. Kratsch, Dieter Timmer, Sjoerd T. Univ Utrecht NL-3508 TB Utrecht Netherlands Univ Lorraine Metz LITA F-57045 Metz 01 France

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.

关键词： graph algorithms Exact algorithms Combinatorial games Analysis of algorithms Moderately exponential time algorithms Kayles Independent sets

来源：评论

学校读者我要写书评

暂无评论

COUNTING LIST MATRIX PARTITIONS OF graphS

引用

SIAM JOURNAL ON COMPUTING 2015年第4期44卷 1089-1118页

作者： Goebel, Andreas Goldberg, Leslie Ann Mcquillan, Colin Richerby, David Yamakami, Tomoyuki Univ Oxford Dept Comp Sci Oxford OX1 3QD England Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England Univ Fukui Dept Informat Sci Fukui Fukui 9108507 Japan

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

关键词： counting problems complexity dichotomy #P-completeness graph algorithms matrix partitions of graphs

来源：评论

学校读者我要写书评

暂无评论

Fault tolerant additive and (μ, α)-spanners

引用

THEORETICAL COMPUTER SCIENCE 2015年 580卷 94-100页

作者： Braunschvig, Gilad Chechik, Shiri Peleg, David Sealfon, Adam Weizmann Inst Sci Dept Comp Sci & Appl Math Rehovot Israel Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA

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.

关键词： Fault tolerance Spanners Additive spanners graph algorithms

来源：评论

学校读者我要写书评

暂无评论

A greedy topology design to accelerate consensus in broadcast wireless sensor networks

引用

INFORMATION PROCESSING LETTERS 2015年第3期115卷 408-413页

作者： Vecchio, Massimo Lopez-Valcarce, Roberto CREATE NET I-38123 Trento Italy Univ Vigo Dept Teoria Serial & Comunicac Vigo 36310 Spain

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.

关键词： Average consensus Range assignment Topology control Wireless multicast advantage graph algorithms

来源：评论

学校读者我要写书评

暂无评论

An Improved Distributed Algorithm for Maximal Independent Set 16

An Improved Distributed Algorithm for Maximal Independent Se...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Mohsen Ghaffari MIT

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.

关键词： Management Information Systems distributed algorithms randomized algorithms graph algorithms Square root algorithms Probability Complexity

来源：评论

学校读者我要写书评

暂无评论

An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality

引用

INFORMATION PROCESSING LETTERS 2015年第11期115卷 866-871页

作者： Moemke, Tobias Univ Saarland D-66123 Saarbrucken Germany

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.

关键词： algorithms Analysis of algorithms Approximation algorithms Design of algorithms graph algorithms Relaxed triangle inequality TSP

来源：评论

学校读者我要写书评

暂无评论

Hardness results, approximation and exact algorithms for liar's domination problem in graphs

引用

THEORETICAL COMPUTER SCIENCE 2015年 573卷 26-42页

作者： Panda, B. S. Paul, S. Pradhan, D. Indian Inst Technol Delhi Dept Math Comp Sci & Applicat Grp New Delhi 110016 India Indian Inst Technol Jodhpur 342011 Rajasthan India

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.

关键词： graph algorithms NP-completeness APX-completeness Approximation algorithms Domination Liar's domination Chordal graph

来源：评论

学校读者我要写书评

暂无评论

Vertex coloring edge-weighted digraphs

引用

INFORMATION PROCESSING LETTERS 2015年第10期115卷 791-796页

作者： Bang-Jensen, Jorgen Halldorsson, Magnus M. Univ Southern Denmark Dept Math & Comp Sci Odense Denmark Reykjavik Univ Sch Comp Sci ICE TCS IS-101 Reykjavik Iceland

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.

关键词： graph algorithms Coloring Edge-weighted digraphs Wireless scheduling

来源：评论

学校读者我要写书评

暂无评论

The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones

引用

INFORMATION PROCESSING LETTERS 2015年第2期115卷 232-236页

作者： Janczewski, Robert Turowski, Krzysztof Gdansk Univ Technol Dept Algorithms & Syst Modelling Gdansk Poland

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.

关键词： Bounded-degree graphs Backbone chromatic number graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Responsive algorithms for Handling Load Surges and Switching Links On in Green Networks

Responsive Algorithms for Handling Load Surges and Switching...

引用

Ad-Hoc and Sensor Networks Symposium

作者： Radu CARPA Marcos Dias de ASSUNCAO Olivier GLUCK Laurent LEFEVRE Jean-Christophe MIGNOT Inria Avalon - LIP Laboratory - Ecole normale superieure of Lyon University of Lyon

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.

关键词： Turning Network Congestion network capacity graph algorithms computer network Energy efficiency Surges MILLISECOND Traffic Network network node switching execution time

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：