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

Guard games on graphs: Keep the intruder out!

THEORETICAL COMPUTER SCIENCE 2011年第46期412卷 6484-6497页

作者： Fomin, Fedor V. Golovach, Petr A. Lokshtanov, Daniel Univ Durham Sch Engn & Comp Sci Durham DH1 3LE England Univ Bergen Dept Informat N-5020 Bergen Norway Univ Calif San Diego La Jolla CA 92093 USA

A team of mobile agents, called guards, tries to keep an intruder out of an assigned area by blocking all possible attacks. In a graph model for this setting, the guards and the intruder are located on the vertices of a graph, and they move from node to node via connecting edges. The area protected by the guards is an induced subgraph of the given graph. We investigate the algorithmic aspects of the guarding problem, which is to find the minimum number of guards sufficient to patrol the area. We show that the guarding problem is PSPACE-hard and provide a set of approximation algorithms. All approximation algorithms are based on the study of a variant of the game where the intruder must reach the guarded area in a single step in order to win. This variant of the game appears to be a 2-approximation for the guarding problem, and for graphs without cycles of length 5 the minimum number of required guards in both games coincides. We give a polynomial time algorithm for solving the one-step guarding problem in graphs of bounded treewidth, and complement this result by showing that the problem is W[1]-hard parameterized by the treewidth of the input graph. We also show that the problem is fixed parameter tractable (FPT) parameterized by the treewidth and maximum degree of the input graph. Finally, we turn our attention to a large class of sparse graphs, including planar graphs and graphs of bounded genus, namely apex-minor-free graphs. We prove that the one-step guarding problem is FPT and possess a PTAS on apex-minor-free graphs. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Guard games complexity parameterized complexity Approximation

来源：评论

学校读者我要写书评

暂无评论

Spanners in sparse graphs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2011年第6期77卷 1108-1119页

作者： Dragan, Feodor F. Fomin, Fedor V. Golovach, Petr A. Kent State Univ Dept Comp Sci Kent OH 44242 USA Univ Bergen Dept Informat N-5020 Bergen Norway Univ Durham Sch Engn & Comp Sci Durham DH1 3LE England

A t-spanner of a graph G is a spanning subgraph S in which the distance between every pair of vertices is at most t times their distance in G. If S is required to be a tree then S is called a tree t-spanner of G. In 1998, Fekete and Kremer showed that on unweighted planar graphs deciding whether G admits a tree t-spanner is polynomial time solvable for t <= 3 and is NP-complete when t is part of the input. They also left as an open problem if the problem is polynomial time solvable for every fixed t >= 4. In this work we resolve the open question of Fekete and Kremer by proving much more general results: The problem of finding a t-spanner of treewidth at most k in a given planar graph G is fixed parameter tractable parameterized by k and t. Moreover, for every fixed t and k, the running time of our algorithm is linear. Our technique allows to extend the result from planar graphs to much more general classes of graphs. An apex graph is a graph that can be made planar by the removal of a single vertex. We prove that the problem of finding a t-spanner of treewidth k is fixed parameter tractable on graphs that do not contain some fixed apex graph as a minor, i.e. on apex-minor-free graphs. The class of apex-minor-free graphs contains planar graphs and graphs of bounded genus. Finally, we show that the tractability, border of the t-spanner problem cannot be extended beyond the class of apex-minor-free graphs and in this sense our results are tight. In particular, for every t >= 4, the problem of finding a tree t-spanner is NP-complete on K-6-minor-free graphs. (C) 2010 Elsevier Inc. All rights reserved.

关键词： Graph algorithms parameterized complexity Spanners Distances Planar graphs Apex-minor-free graphs Treewidth

来源：评论

学校读者我要写书评

暂无评论

Faster parameterized algorithms for minor containment

引用

THEORETICAL COMPUTER SCIENCE 2011年第50期412卷 7018-7028页

作者： Adler, Isolde Dorn, Frederic Fomin, Fedor V. Sau, Ignasi Thilikos, Dimitrios M. CNRS LIRMM AIGCo Project Team Montpellier France Goethe Univ Frankfurt Inst Informat Frankfurt Germany Univ Bergen Dept Informat N-5020 Bergen Norway Natl & Kapodistrian Univ Dept Math Athens Greece

The H-MINOR CONTAINMENT problem asks whether a graph G contains some fixed graph H as a minor, that is, whether H can be obtained by some subgraph of G after contracting edges. The derivation of a polynomial-time algorithm for H-MINOR CONTAINMENT is one of the most important and technical parts of the Graph Minor Theory of Robertson and Seymour and it is a cornerstone for most of the algorithmic applications of this theory. H-MINOR CONTAINMENT for graphs of bounded branchwidth is a basic ingredient of this algorithm. The currently fastest solution to this problem, based on the ideas introduced by Robertson and Seymour, was given by Hicks in [I.V. Hicks, Branch decompositions and minor containment, Networks 43 (1) (2004) 1-9], providing an algorithm that in time 0(3(k2) . (h+k-1)!.m) decides if a graph G with m edges and branchwidth k, contains a fixed graph H on h vertices as a minor. In this work we improve the dependence on k of Hicks' result by showing that checking if H is a minor of G can be done in time O(2((2k+1).log k) h(2k) . 2(2h2) m). We set up an approach based on a combinatorial object called rooted packing, which captures the properties of the subgraphs of H that we seek in our dynamic programming algorithm. This formulation with rooted packings allows us to speed up the algorithm when G is embedded in a fixed surface, obtaining the first algorithm for minor containment testing with single-exponential dependence on branchwidth. Namely, it runs in time 2(O(k)) . 2(O(k)) . 2(O(h)) . n, with n = vertical bar V(G) vertical bar. Finally, we show that slight modifications of our algorithm permit to solve some related problems within the same time bounds, like induced minor or contraction containment. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Graph minors Branchwidth Graph minor containment parameterized complexity Dynamic programming Graphs on surfaces

来源：评论

学校读者我要写书评

暂无评论

A kernel of order 2k-c log k for vertex cover

引用

INFORMATION PROCESSING LETTERS 2011年第23-24期111卷 1089-1091页

作者： Lampis, Michael CUNY Grad Ctr New York NY 10021 USA

In a recent paper Soleimanfallah and Yeo proposed a kernelization algorithm for vertex cover which, for any fixed constant c, produces a kernel of order 2k - c in polynomial time. In this paper we show how their techniques can be extended to improve the produced kernel to order 2k - c log k, for any fixed constant c. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Graph algorithms parameterized complexity Kernelization algorithm Vertex cover

来源：评论

学校读者我要写书评

暂无评论

On the directed Full Degree Spanning Tree problem

引用

DISCRETE OPTIMIZATION 2011年第1期8卷 97-109页

作者： Lokshtanov, Daniel Raman, Venkatesh Saurabh, Saket Sikdar, Somnath Univ Bergen N-5020 Bergen Norway

We study the parameterized complexity of a directed analog of the FULL DEGREE SPANNING TREE problem where, given a digraph D and a nonnegative integer k, the goal is to construct a spanning out-tree T of D such that at least k vertices in T have the same out-degree as in D. We show that this problem is W[1]-hard even on the class of directed acyclic graphs. In the dual version, called REDUCED DEGREE SPANNING TREE, one is required to construct a spanning out-tree T such that at most k vertices in T have out-degrees that are different from that in D. We show that this problem is fixed-parameter tractable and that it admits a problem kernel with at most 8k vertices on strongly connected digraphs and O(k(2)) vertices on general digraphs. We also give an algorithm for this problem on general digraphs with running time O(5.942(k) . n(O(1))), where n is the number of vertices in the input digraph. (C) 2010 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Kernelization Full Degree Spanning Tree

来源：评论

学校读者我要写书评

暂无评论

Hardness of subgraph and supergraph problems in c-tournaments

引用

THEORETICAL COMPUTER SCIENCE 2011年第35期412卷 4629-4635页

作者： Kiran, S. Kanthi Narayanaswamy, N. S. IIT Madras Dept Comp Sci & Engn Madras 600036 Tamil Nadu India

Problems like the directed feedback vertex set problem have much better algorithms in tournaments when compared to general graphs. This motivates us to study a natural generalization of tournaments, named c-tournaments, and see if the structural properties of these graphs are helpful in obtaining similar algorithms, c-tournaments are simple digraphs which have directed paths of length at most c >= 1 between all pairs of vertices. We study the complexity of feedback vertex set and r-dominating set in c-tournaments. We also present hardness results on some graph editing problems involving c-tournaments. (C) 2011 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Feedback vertex set Dominating set Graph modification Tournaments

来源：评论

学校读者我要写书评

暂无评论

parameterized Problems Related to Seidel's Switching

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2011年第2期13卷 19-42页

作者： Jelinkova, Eva Suchy, Ondrej Hlineny, Petr Kratochvil, Jan Charles Univ Prague Fac Math & Phys Dept Appl Math Prague Czech Republic Charles Univ Prague Fac Math & Phys Inst Theoret Comp Sci Prague Czech Republic Univ Saarland D-6600 Saarbrucken Germany Masaryk Univ Fac Informat Brno Czech Republic

Seidel's switching is a graph operation which makes a given vertex adjacent to precisely those vertices to which it was non-adjacent before, while keeping the rest of the graph unchanged. Two graphs are called switching-equivalent if one can be made isomorphic to the other by a sequence of switches. In this paper, we continue the study of computational complexity aspects of Seidel's switching, concentrating on Fixed Parameter complexity. Among other results we show that switching to a graph with at most k edges, to a graph of maximum degree at most k, to a k-regular graph, or to a graph with minimum degree at least k are fixed parameter tractable problems, where k is the parameter. On the other hand, switching to a graph that contains a given fixed graph as an induced subgraph is W [1]-complete. We also show the NP-completeness of switching to a graph with a clique of linear size, and of switching to a graph with small number of edges. A consequence of the latter result is the NP-completeness of Maximum Likelihood Decoding of graph theoretic codes based on complete graphs.

关键词： Seidel's Switching Computational complexity parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Even faster parameterized cluster deletion and cluster editing

引用

INFORMATION PROCESSING LETTERS 2011年第14期111卷 717-721页

作者： Boecker, Sebastian Damaschke, Peter Chalmers Univ Dept Comp Sci & Engn S-41296 Gothenburg Sweden Univ Jena Lehrstuhl Bioinformat D-07743 Jena Germany

CLUSTER DELETION and CLUSTER EDITING ask to transform a graph by at most k edge deletions or edge edits, respectively, into a cluster graph, i.e., disjoint union of cliques. Equivalently, a cluster graph has no conflict triples, i.e., two incident edges without a transitive edge. We solve the two problems in time O*(1.415(k)) and O*(1.76(k)), respectively. These results round off our earlier work by considerably improved time bounds. For CLUSTER DELETION we use a technique that cuts away small connected components that do no longer contribute to the exponential part of the time complexity. As this idea is simple and versatile, it may lead to improvements for several other parameterized graph problems. The improvement for CLUSTER EDITING is achieved by using the full power of an earlier structure theorem for graphs where no edge is in three conflict triples. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Cluster editing parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On the small cycle transversal of planar graphs

引用

THEORETICAL COMPUTER SCIENCE 2011年第29期412卷 3501-3509页

作者： Xia, Ge Zhang, Yong Lafayette Coll Dept Comp Sci Easton PA 18042 USA Kutztown State Univ Dept Comp Sci Kutztown PA 19530 USA

We consider the problem of finding a k-edge transversal set that intersects all (simple) cycles of length at most s in a planar graph, where s >= 3 is a constant, This problem, referred to as SMALL CYCLE TRANSVERSAL, is known to be NP-complete. We present a polynomial-time algorithm that computes a kernel of size 36s(3) k for SMALL CYCLE TRANSVERSAL. In order to achieve this kernel, we extend the region decomposition technique of Alber et al. (2004) [1] by considering a unique region decomposition that is defined by shortest paths. Our kernel size is a significant improvement in terms of s over the kernel size obtained under the meta-kernelization framework by Bodlaender et al. (2009) [7]. (C) 2011 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Kernelization Planar graphs Cycle transversal

来源：评论

学校读者我要写书评

暂无评论

Confronting intractability via parameters

引用

COMPUTER SCIENCE REVIEW 2011年第4期5卷 279-317页

作者： Downey, Rodney G. Thilikos, Dimitrios M. Victoria Univ Sch Math Stat & Operat Res Wellington New Zealand Univ Athens Dept Math Panepistimioupolis GR-15784 Athens Greece

One approach to confronting computational hardness is to try to understand the contribution of various parameters to the running time of algorithms and the complexity of computational tasks. Almost no computational tasks in real life are specified by their size alone. It is not hard to imagine that some parameters contribute more intractability than others and it seems reasonable to develop a theory of computational complexity which seeks to exploit this fact. Such a theory should be able to address the needs of practitioners in algorithmics. The last twenty years have seen the development of such a theory. This theory has a large number of successes in terms of a rich collection of algorithmic techniques, both practical and theoretical, and a fine-grained intractability theory. Whilst the theory has been widely used in a number of areas of applications including computational biology, linguistics, VLSI design, learning theory and many others, knowledge of the area is highly varied. We hope that this article will show the basic theory and point at the wide array of techniques available. Naturally the treatment is condensed, and the reader who wants more should go to the texts of Downey and Fellows (1999) [2], Flum and Grohe (2006) [59], Niedermeier (2006) [28], and the upcoming undergraduate text (Downey and Fellows 2012) [278]. (C). 2011 Elsevier Inc. All rights reserved.

关键词： parameterized complexity parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：