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

Space Saving by Dynamic Algebraization Based on Tree-Depth

THEORY OF COMPUTING SYSTEMS 2017年第2期61卷 283-304页

作者： Furer, Martin Yu, Huiwen Penn State Univ Dept Comp Sci & Engn University Pk PA 16802 USA Google Inc 1600 Amphitheatre Pkwy Mountain View CA USA Penn State Univ University Pk PA 16802 USA

Dynamic programming is widely used for exact computations based on tree decompositions of graphs. However, the space complexity is usually exponential in the treewidth. We study the problem of designing efficient dynamic programming algorithms based on tree decompositions in polynomial space. We show how to use a tree decomposition and extend the algebraic techniques of Lokshtanov and Nederlof (In: 42nd ACM Symposium on Theory of Computing, pp. 321-330, 2010) such that a typical dynamic programming algorithm runs in time O*(2h), where h is the treedepth (Nesetril et al., Eur. J. Comb. 27( 6): 1022-1041, 2006) of a graph. In general, we assume that a tree decomposition of depth h is given. We apply our algorithm to the problem of counting perfect matchings on grids and show that it outperforms other polynomial-space solutions. We also apply the algorithm to other set covering and partitioning problems.

关键词： Dynamic programming Tree-depth Tree decomposition Space-efficient algorithms exponential time algorithms Zeta transform

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for the Maximum Leaf Spanning Tree problem

引用

THEORETICAL COMPUTER SCIENCE 2011年第45期412卷 6290-6302页

作者： Fernau, Henning Kneis, Joachim Kratsch, Dieter Langer, Alexander Liedloff, Mathieu Raible, Daniel Rossmanith, Peter Univ Orleans Lab Informat Fondamentale Orleans F-45067 Orleans 2 France Univ Trier FB Abt Informat 4 D-54286 Trier Germany Rhein Westfal TH Aachen Dept Comp Sci Aachen Germany Univ Paul Verlaine Metz Lab Informat Theor & Appl F-57045 Metz 01 France

Given an undirected graph with n vertices, the MAXIMUM LEAF SPANNING TREE problem is to find a spanning tree with as many leaves as possible. When parameterized in the number of leaves k, this problem can be solved in time O(4(k)poly(n)) using a simple branching algorithm introduced by a subset of the authors (Kneis et al. 2008 [16]). Daligault et al. (2010) [16] improved the branching and obtained a running time of O(3.72(k)poly(n)). In this paper, we study the problem from an exponential time viewpoint, where it is equivalent to the CONNECTED DOMINATING SET problem. Here, Fomin, Grandoni, and Kratsch showed how to break the Omega(2(n)) barrier and proposed an O(1.9407(n))-time algorithm (Fomin et al. 2008 [11]). Based on some useful properties of Kneis et al. (2008) [16] and Daligault et al. (2010) [6], we present a branching algorithm whose running time of O(1.8966(n)) has been analyzed using the Measure-and-Conquer technique. Finally, we provide a lower bound of Omega(1.4422(n)) for the worst case running time of our algorithm. (C) 2011 Elsevier B.V. All rights reserved.

关键词： exponential time algorithms Graph algorithms Spanning tree Maximum Leaf Spanning Tree

来源：评论

学校读者我要写书评

暂无评论

A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2012年第1期14卷 29-42页

作者： Gaspers, Serge Liedloff, Mathieu Vienna Univ Technol Inst Informat Syst A-1040 Vienna Austria Univ Orleans Lab Informat Fondamentale Orleans Orleans France

An independent dominating set D of a graph G = (V, E) is a subset of vertices such that every vertex in V \ D has at least one neighbor in D and D is an independent set, i.e. no two vertices of D are adjacent in G. Finding a minimum independent dominating set in a graph is an NP-hard problem. Whereas it is hard to cope with this problem using parameterized and approximation algorithms, there is a simple exact O(1.4423(n))-time algorithm solving the problem by enumerating all maximal independent sets. In this paper we improve the latter result, providing the first non-trivial algorithm computing a minimum independent dominating set of a graph in time O(1.3569(n)). Furthermore, we give a lower bound of Omega(1.3247(n)) on the worst-case running time of this algorithm, showing that the running time analysis is almost tight.

关键词： exponential time algorithms minimum independent dominating set minimum maximal independent set

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for the minimum dominating clique problem

引用

THEORETICAL COMPUTER SCIENCE 2007年第1-3期385卷 226-240页

作者： Kratsch, Dieter Liedloff, Mathieu Univ Paul Verlaine Metz Dept Informat Lab Informat Theor & Appl F-57045 Metz 01 France

A subset of vertices D subset of V of a graph G = (V, E) is a dominating clique if D is a dominating set and a clique of G. The existence problem 'Given a graph G, is there a dominating clique in G?' is NP-complete, and thus both the Minimum and the Maximum Dominating Clique problems are NP-hard. We present an O(1.3387(n)) time and polynomial space algorithm that for an input graph on n vertices either computes a minimum dominating clique or reports that the graph has no dominating clique. The algorithm uses the Branch & Reduce paradigm and its time analysis is based on the Measure & Conquer approach. We also establish a lower bound of Omega(1.2599(n)) for the worst case running time of the algorithm. Finally using memorization we obtain an O(1.3234(n)) time and exponential space algorithm for the same problem. (c) 2007 Elsevier B.V. All rights reserved.

关键词： graph algorithms exponential time algorithms dominating clique dominating set

来源：评论

学校读者我要写书评

暂无评论

Faster Graph Coloring in Polynomial Space

引用

ALGORITHMICA 2023年第2期85卷 584-609页

作者： Gaspers, Serge Lee, Edward J. UNSW Sydney Sydney NSW Australia

We present a polynomial-space algorithm that computes the number of independent sets of any input graph in time O(1.1389(n)) for graphs with maximum degree 3 and in time O(1.2356(n)) for general graphs, where n is the number of vertices in the input graph. Together with the inclusion-exclusion approach of Bjorklund, Husfeldt, and Koivisto [SIAM J. Comput. 2009], this leads to a faster polynomial-space algorithm for the graph coloring problem with running time O(2.2356(n)) as well as an exponential-space O(1.2330(n)) time algorithm for counting independent sets. Our main algorithm counts independent sets in graphs with maximum degree at most 3 and no vertex with three neighbors of degree 3. This polynomial-space algorithm is designed and analyzed using the recently introduced Separate, Measure and Conquer approach [Gaspers & Sorkin, ICALP 2015]. Using Wahlstrom's compound measure approach, this improvement in running time for small degree graphs is then bootstrapped to larger degrees, giving the improvement for general graphs. Combining both approaches leads to some inflexibility in choosing vertices to branch on for the small-degree cases, which we counter by structural graph properties.

关键词： Graph coloring exponential time algorithms Analysis of algorithms Branching algorithms Counting independent sets

来源：评论

学校读者我要写书评

暂无评论

Exact algorithms for dominating set

引用

DISCRETE APPLIED MATHEMATICS 2011年第17期159卷 2147-2164页

作者： van Rooij, Johan M. M. Bodlaender, Hans L. Univ Utrecht Dept Informat & Comp Sci NL-3508 TB Utrecht Netherlands

The measure and conquer approach has proven to be a powerful tool to analyse exact algorithms for combinatorial problems like DOMINATING SET and INDEPENDENT SET. This approach is used in this paper to obtain a faster exact algorithm for DOMINATING SET. We obtain this algorithm by considering a series of branch and reduce algorithms. This series is the result of an iterative process in which a mathematical analysis of an algorithm in the series with measure and conquer results in a convex or quasiconvex programming problem. The solution, by means of a computer, to this problem not only gives a bound on the running time of the algorithm, but can also give an indication on where to look for a new reduction rule, often giving a new, possibly faster algorithm. As a result, we obtain an O(1.4969(n)) time and polynomial space algorithm. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Exact algorithms exponential time algorithms Branch and reduce Measure and conquer Dominating set Computer aided algorithm design

来源：评论

学校读者我要写书评

暂无评论

Dominating set based exact algorithms for 3-coloring

引用

INFORMATION PROCESSING LETTERS 2011年第6期111卷 251-255页

作者： Narayanaswamy, N. S. Subramanian, C. R. Inst Math Sci Madras 600113 Tamil Nadu India IIT Madras Dept CSE Madras Tamil Nadu India

We show that the 3-colorability problem can be solved in O(1.296(n)) time on any n-vertex graph with minimum degree at least 15. This algorithm is obtained by constructing a dominating set of the graph greedily, enumerating all possible 3-colorings of the dominating set, and then solving the resulting 2-list coloring instances in polynomial time. We also show that a 3-coloring can be obtained in 2(o(n)) time for graphs having minimum degree at least w(n) where w(n) is any function which goes to infinity. We also show that if the lower bound on minimum degree is replaced by a constant (however large it may be), then neither a 2(o(n)) time nor a 2(o(m)) time algorithm is possible (m denotes the number of edges) for 3-colorability unless exponential time Hypothesis (ETH) fails. We also describe an algorithm which obtains a 4-coloring of a 3-colorable graph in O(1.2535(n)) time. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Design of algorithms Graph coloring 3-coloring Exact algorithms exponential time algorithms

来源：评论

学校读者我要写书评

暂无评论

FASTER SPACE-EFFICIENT algorithms FOR SUBSET SUM, k-SUM, AND RELATED PROBLEMS

引用

SIAM JOURNAL ON COMPUTING 2018年第5期47卷 1755-1777页

作者： Bansal, Nikhil Garg, Shashwat Nederlof, Jesper Vyas, Nikhil Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 AB Eindhoven Netherlands MIT Comp Sci & Artificial Intelligence Lab 77 Massachusetts Ave Cambridge MA 02139 USA

We present randomized algorithms that solve subset sum and knapsack instances with n items in O*((20.86n)) time, where the O* (.) notation suppresses factors polynomial in the input size, and polynomial space, assuming random read-only access to exponentially many random bits. These results can be extended to solve binary integer programming on n variables with few constraints in a similar running time. We also show that for any constant k >= 2, random instances of k-sum can be solved using O(n(k-0.5) polylog(n)) time and O(log n) space, without the assumption of random access to random bits. Underlying these results is an algorithm that determines whether two given lists of length n with integers bounded by a polynomial in n share a common value. Assuming random read-only access to random bits, we show that this problem can be solved using O(log n) space significantly faster than the trivial O(n(2)) time algorithm if no value occurs too often in the same list.

关键词： space-efficient algorithms k-sum subset sum exact exponential time algorithms fine-grained complexity space-time trade-off exponential time algorithms

来源：评论

学校读者我要写书评

暂无评论

Exact algorithms for edge domination

引用

3rd International Workshop on Parameterized and Exact Computation

作者： van Rooij, Johan M. M. Bodlaender, Hans L. Univ Utrecht Inst Informat & Comp Sci NL-3508 TB Utrecht Netherlands

ISBN: (纸本)9783540797227

In this paper we present a faster exact exponential time algorithm for the edge dominating set problem. Our algorithm uses O(1.3226(n)) time and polynomial space. The algorithm combines an enumeration approach based on enumerating minimal vertex covers with the branch and reduce paradigm. Its time bound is obtained using the measure and conquer technique. The algorithm is obtained by starting with a slower algorithm which is refined stepwise. In this way a series of algorithms appears, each one slightly faster than the previous, resulting in the O(1.3226(n)) time algorithm. The techniques also gives faster exact algorithms for: minimum weight edge dominating set, minimum (weight) maximal matching, matrix domination and the parametrised version of minimum weight maximal matching.

关键词： edge dominating set minimum maximal matching exact algorithms exponential time algorithms measure and conquer

来源：评论

学校读者我要写书评

暂无评论

On Problems as Hard as CNF-SAT

On Problems as Hard as CNF-SAT

引用

27th Annual IEEE Conference on Computational Complexity (CCC)

作者： Cygan, Marek Dell, Holger Lokshtanov, Daniel Marx, Daniel Nederlof, Jesper Okamoto, Yoshio Paturi, Ramamohan Saurabh, Saket Wahlstroem, Magnus Univ Lugano IDSIA Lugano Switzerland Univ Wisconsin Madison WI 53706 USA Univ Calif Oakland CA USA Hungarian Acad Sci Comp & Automat Res Inst Budapest Hungary Univ Utrecht NL-3508 TC Utrecht Netherlands Japan Adv Inst Sci & Technol Kanazawa Ishikawa Japan Inst Math Sci Hyderabad Andhra Pradesh India Max Planck Inst Informat Saarbrucken Germany

ISBN: (纸本)9780769547084;9781467316637

The field of exact exponential time algorithms for NP-hard problems has thrived over the last decade. While exhaustive search remains asymptotically the fastest known algorithm for some basic problems, difficult and non-trivial exponential time algorithms have been found for a myriad of problems, including GRAPH COLORING, HAMILTONIAN PATH, DOMINATING SET and 3-CNF-SAT. In some instances, improving these algorithms further seems to be out of reach. The CNF-SAT problem is the canonical example of a problem for which the trivial exhaustive search algorithm runs in time O(2(n)), where n is the number of variables in the input formula. While there exist non-trivial algorithms for CNF-SAT that run in time o(2(n)), no algorithm was able to improve the growth rate 2 to a smaller constant, and hence it is natural to conjecture that 2 is the optimal growth rate. The strong exponential time hypothesis (SETH) by Impagliazzo and Paturi [JCSS 2001] goes a little bit further and asserts that, for every epsilon < 1, there is a (large) integer k such that that K-CNF-SAT cannot be computed in time 2(epsilon n). In this paper, we show that, for every epsilon < 1, the problems HITTING SET, SET SPLITTING, and NAE-SAT cannot be computed in time O(2(epsilon n)) unless SETH fails. Here n is the number of elements or variables in the input. For these problems, we actually get an equivalence to SETH in a certain sense. We conjecture that SETH implies a similar statement for SET COVER, and prove that, under this assumption, the fastest known algorithms for STEINTER TREE, CONNECTED VERTEX COVER, SET PARTITIONING, and the pseudo-polynomial time algorithm for SUBSET SUM cannot be significantly improved. Finally, we justify our assumption about the hardness of SET COVER by showing that the parity of the number of set covers cannot be computed in time O(2(epsilon n)) for any epsilon < 1 unless SETH fails.

关键词： Strong exponential time Hypothesis exponential time algorithms Sparsification Lemma

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：