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

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

来源：评论

学校读者我要写书评

暂无评论

An Exact exponential time Algorithm for Power Dominating Set

引用

ALGORITHMICA 2012年第1-2期63卷 323-346页

作者： Binkele-Raible, Daniel Fernau, Henning Univ Trier FB Abt Informat Wirtschaftsinformat 4 Trier Germany

The POWER DOMINATING SET problem is an extension of the well-known domination problem on graphs in a way that we enrich it by a second propagation rule: given a graph G(V, E), a set P subset of V is a power dominating set if every vertex is observed after the exhaustive application of the following two rules. First, a vertex is observed if v. P or it has a neighbor in P. Secondly, if an observed vertex has exactly one unobserved neighbor u, then also u will be observed, as well. We show that POWER DOMINATING SET remains NP-hard on cubic graphs. We design an algorithm solving this problem in time O*(1.7548(n)) on general graphs, using polynomial space only. To achieve this, we introduce so-called reference search trees that can be seen as a compact representation of usual search trees, providing non-local pointers in order to indicate pruned subtrees.

关键词： Domination-type problems moderately exponential time algorithms NP-hardness results Measure and conquer

来源：评论

学校读者我要写书评

暂无评论

FINDING INDUCED SUBGRAPHS VIA MINIMAL TRIANGULATIONS

FINDING INDUCED SUBGRAPHS VIA MINIMAL TRIANGULATIONS

引用

27th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Fomin, Fedor V. Villanger, Yngve Univ Bergen Dept Informat Bergen Norway

ISBN: (纸本)9783939897163

Potential maximal cliques and minimal separators are combinatorial objects which were introduced and studied in the realm of minimal triangulation problems including Minimum Fill-in and Treewidth. We discover unexpected applications of these notions to the field of moderate exponential algorithms. In particular, we show that given an n-vertex graph G together with its set of potential maximal cliques, and an integer t, it is possible in time the number of potential maximal cliques times O(n(O(t))) to find a maximum induced subgraph of treewidth t in G and for a given graph F of treewidth t, to decide if G contains an induced subgraph isomorphic to F. Combined with an improved algorithm enumerating all potential maximal cliques in time O(1.734601(n)), this yields that both the problems are solvable in time 1.734601(n) * n(O(t)).

关键词： Bounded treewidth minimal triangulation moderately exponential time algorithms

来源：评论

学校读者我要写书评

暂无评论

EXACT COVERS VIA DETERMINANTS

EXACT COVERS VIA DETERMINANTS

引用

27th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Bjorklund, Andreas

ISBN: (纸本)9783939897163

Given a k-uniform hypergraph on n vertices, partitioned in k equal parts such that every hyperedge includes one vertex from each part, the k-Dimensional Matching problem asks whether there is a disjoint collection of the hyperedges which covers all vertices. We show it can be solved by a randomized polynomial space algorithm in O*(2(n(k-2)/k)) time. The O*() notation hides factors polynomial in n and k. The general Exact Cover by k-Sets problem asks the same when the partition constraint is dropped and arbitrary hyperedges of cardinality k are permitted. We show it can be solved by a randomized polynomial space algorithm in O *(c(k)(n)) time, where c(3) = 1.496, c(4) = 1.642, c(5) = 1.721, and provide a general bound for larger k. Both results substantially improve on the previous best algorithms for these problems, especially for small k. They follow from the new observation that Lovasz' perfect matching detection via determinants (Lovasz, 1979) admits an embedding in the recently proposed inclusion-exclusion counting scheme for set covers, despite its inability to count the perfect matchings.

关键词： moderately exponential time algorithms Exact Set Cover k-Dimensional Matching

来源：评论

学校读者我要写书评

暂无评论

exponential time algorithms for the Minimum Dominating Set Problem on Some Graph Classes

引用

ACM TRANSACTIONS ON algorithms 2009年第1期6卷 1–21页

作者： Gaspers, Serge Kratsch, Dieter Liedloff, Mathieu Todinca, Ioan Univ Chile Ctr Modelamiento Matemat Santiago 8370459 Chile Univ Paul Verlaine Lab Informat Theor & Appl F-57045 Metz 01 France Univ Orleans Lab Informat Fondamentale Orleans F-45067 Orleans 2 France

The minimum dominating set problem remains NP-hard when restricted to any of the following graph classes: c-dense graphs, chordal graphs, 4-chordal graphs, weakly chordal graphs, and circle graphs. Developing and using a general approach, for each of these graph classes we present an exponential time algorithm solving the minimum dominating set problem faster than the best known algorithm for general graphs. Our algorithms have the following running time: O(1.4124(n)) for chordal graphs, O(1.4776(n)) for weakly chordal graphs, O(1.4845(n)) for 4-chordal graphs, O(1.4887(n)) for circle graphs, and O(1.2273((1+root 1-2c)n)) for c-dense graphs.

关键词： moderately exponential time algorithms dominating set problem graph classes

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：