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

Counting models for 2_SAT and 3_SAT formulae

THEORETICAL COMPUTER SCIENCE 2005年第1-3期332卷 265-291页

作者： Dahllöf, V Jonsson, P Wahström, M Linkoping Univ Dept Comp & Informat Sci SE-58183 Linkoping Sweden

We here present algorithms for counting models and max-weight models for 2SAT and 3SAT formulae. They use polynomial space and run in O(1.2561(n)) and O(1.6737(n)) time, respectively, where n is the number of variables. This is faster than the previously best algorithms for counting nonweighted models for 2SAT and 3SAT, which run in O(1.3247(n)) and O(1.6894(n)) time, respectively. In order to prove these time bounds, we develop new measures of formula complexity, allowing us to conveniently analyze the effects of certain factors with a large impact on the total running time. We also provide an algorithm for the restricted case of separable 2SAT formulae, with fast running times for well-studied input classes. For all three algorithms we present interesting applications, such as computing the permanent of sparse 0/1 matrices. (c) 2004 Elsevier B.V. All rights reserved.

关键词： counting models satisfiability exponential-time algorithms exact algorithms upper bounds

来源：评论

学校读者我要写书评

暂无评论

Improved bounds for minimal feedback vertex sets in tournaments

引用

JOURNAL OF GRAPH THEORY 2018年第3期88卷 482-506页

作者： Mnich, M. Teutrine, E. Univ Bonn Inst Informat Bonn Germany Maastricht Univ Dept Quantitat Econ Maastricht Netherlands

We study feedback vertex sets (FVS) in tournaments, which are orientations of complete graphs. As our main result, we show that any tournament on n nodes has at most 1.5949(n) minimal FVS. This significantly improves the previously best upper bound of 1.6667(n) by Fomin etal. [STOC 2016] and 1.6740(n) by Gaspers and Mnich [J. Graph Theory72(1):72-89, 2013]. Our new upper bound almost matches the best-known lower bound of 21n/7 approximate to 1.5448n, due to Gaspers and Mnich. Our proof is algorithmic, and shows that all minimal FVS of tournaments can be enumerated in time O(1.5949(n)).

关键词： combinatorial bounds exponential-time algorithms feedback vertex sets tournaments

来源：评论

学校读者我要写书评

暂无评论

On the number of minimal dominating sets on some graph classes

引用

THEORETICAL COMPUTER SCIENCE 2015年第C期562卷 634-642页

作者： Couturier, Jean-Francois Letourneur, Romain Liedloff, Mathieu CReSTIC IFTS Pole Haute Technol F-08000 Charleville Mezieres France Univ Orleans INSA Ctr Val Loire LIFO EA 4022 FR-45067 Orleans France

A dominating set in a graph is a subset of vertices such that each vertex is either in the dominating set or adjacent to some vertex in the dominating set. It is known that graphs have at most O(1.7159(n)) minimal dominating sets. In this paper, we establish upper bounds on this maximum number of minimal dominating sets for split graphs, cobipartite graphs and interval graphs. For each of these graph classes, we provide an algorithm to enumerate them. For split and interval graphs, we show that the number of minimal dominating sets is at most 3(n/3) approximate to 1.4423(n), which is the best possible bound. This settles a conjecture by Couturier et al. (SOFSEM 2012, [11). For cobipartite graphs, we lower the O(1.5875(n)) upper bound from Couturier et al. to O(1.4511(n)). (C) 2014 Elsevier B.V. All rights reserved.

关键词： Graph algorithms exponential-time algorithms Graph classes Dominating sets Enumerating algorithms

来源：评论

学校读者我要写书评

暂无评论

On an extension of the Sort & Search method with application to scheduling theory

引用

THEORETICAL COMPUTER SCIENCE 2013年 511卷 13-22页

作者： Lente, Ch Liedloff, M. Soukhal, A. T'Kindt, V. Univ Tours Lab Informat Equipe Ordonnancement & Conduite CNRSERL 6305EA 6300 F-37200 Tours France Univ Orleans Lab Informat Fondamentale Orleans F-45067 Orleans 2 France

In this paper, we focus on the Sort & Search method initially proposed by Horowitz and Sahni (1974) [6] to solve the knapsack problem, which has already show its applicability to derive exponential-time algorithms for some scheduling problems. We propose an extension of this method to a general class of problems called Multiple Constraint Problems and show that the extended Sort & Search method enables one to derive new exponential-time algorithms, with O*(m(n/2)) worst-case complexity, for two scheduling problems. (C) 2013 Elsevier B.V. All rights reserved.

关键词： exponential-time algorithms Scheduling Sort & Search

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for the Boolean connectivity problem for k-CNF

引用

THEORETICAL COMPUTER SCIENCE 2011年第35期412卷 4613-4618页

作者： Makino, Kazuhisa Tamaki, Suguru Yamamoto, Masaki Kyoto Univ Grad Sch Informat Kyoto 6068501 Japan Univ Tokyo Grad Sch Informat Sci & Technol Tokyo 1138654 Japan Kwansei Gakuin Univ Dept Informat Nishinomiya Hyogo Japan

We present an exact algorithm for a PSPACE-complete problem, denoted by CONNkSAT, which asks whether the solution space for a given k-CNF formula is connected on the n-dimensional hypercube. The problem is known to be PSPACE-complete for k >= 3, and polynomial solvable for k <= 2 (Gopalan et al., 2009) [6]. We show that CONNkSAT for k >= 3 is solvable in time O((2 - epsilon(k))(n)) for some constant epsilon(k) > 0, where epsilon(k) depends only on k, but not on n. This result is considered to be interesting due to the following fact shown by Calabro [5]: QBF-3-SAT, which is a typical PSPACE-complete problem, is not solvable in time O((2 - epsilon)(n)) for any constant epsilon > 0, provided that the SAT problem (with no restriction to the clause length) is not solvable in time O((2 - epsilon)(n)) for any constant epsilon > 0. (C) 2011 Elsevier B.V. All rights reserved.

关键词： exponential-time algorithms Boolean connectivity CNF satisfiability

来源：评论

学校读者我要写书评

暂无评论

CONVEX CHARACTERS, algorithms, AND MATCHINGS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2024年第1期38卷 380-411页

作者： Kelk, Steven Meuwese, Ruben Wagner, Stephan Maastricht Univ Dept Adv Comp Sci DACS NL-6200 Maastricht Netherlands Uppsala Univ Dept Math Uppsala Sweden

Phylogenetic trees are used to model evolution: leaves are labeled to represent contemporary species (``taxa""), and interior vertices represent extinct ancestors. Informally, convex characters are measurements on the contemporary species in which the subset of species (both contemporary and extinct) that share a given state form a connected subtree. Kelk and Stamoulis [Adv. Appl. Math., 84 (2017), pp. 34--46] showed how to efficiently count, list, and sample certain restricted subfamilies of convex characters, and algorithmic applications were given. We continue this work in a number of directions. First, we show how combining the enumeration of convex characters with existing parameterized algorithms can be used to speed up exponential-time algorithms for the maximum agreement forest problem in phylogenetics. Second, we revisit the quantity g2(T), defined as the number of convex characters on T in which each state appears on at least 2 taxa. We use this to give an algorithm with running time O(\phi n \cdot poly(n)), where \phi \approx 1.6181 is the golden ratio and n is the number of taxa in the input trees for computation of maximum parsimony distance on two state characters. By further restricting the characters counted by g2(T) we open an interesting bridge to the literature on enumeration of matchings. By crossing this bridge we improve the running time of the aforementioned parsimony distance algorithm to O(1.5895n \cdot poly(n)) and obtain a number of new results in themselves relevant to enumeration of matchings on at most binary trees.

关键词： phylogenetics matchings enumeration combinatorics exponential-time algorithms agreement forests

来源：评论

学校读者我要写书评

暂无评论

Finding a dominating set on bipartite graphs

引用

INFORMATION PROCESSING LETTERS 2008年第5期107卷 154-157页

作者： Liedloff, Mathieu Univ Paul Verlaine Merz Lab Informat Theor & Appl F-57045 Merz 01 France

Finding a dominating set of minimum cardinality is an NP-hard graph problem, even when the graph is bipartite. In this paper we are interested in solving the problem on graphs having a large independent set. Given a graph G with an independent set of size z, we show that the problem can be solved in time O* (2(n-z)), where n is the number of vertices of G. As a consequence, our algorithm is able to solve the dominating set problem on bipartite graphs in time O*(2(n/2)). Another implication is an algorithm for general graphs whose running time is O(1.7088(n)). (C) 2008 Elsevier B.V. All rights reserved.

关键词： graph algorithms dominating set bipartite graphs algorithms exponential-time algorithms

来源：评论

学校读者我要写书评

暂无评论

exponential-time approximation of weighted set cover

引用

INFORMATION PROCESSING LETTERS 2009年第16期109卷 957-961页

作者： Cygan, Marek Kowalik, Lukasz Wykurz, Mateusz Univ Warsaw Inst Informat PL-00325 Warsaw Poland

The SET COVER problem belongs to a group of hard problems which are neither approximable in polynomial time (at least with a constant factor) nor fixed parameter tractable, under widely believed complexity assumptions. In recent years, many researchers design exact exponential-time algorithms for problems of that kind. The goal is getting the time complexity still of order O(c(n)), but with the constant c as small as possible. In this work we extend this line of research and we investigate whether the constant c can be made even smaller when one allows constant factor approximation. In fact, we describe a kind of approximation schemes-trade-offs between approximation factor and the time complexity. We use general transformations from exponential-time exact algorithms to approximations that are faster but still exponential-time. For example, we show that for any reduction rate r, one can transform any O*(c(n))-time(1) algorithm for SET COVER into a (1 + lnr)-approximation algorithm running in time O*(C-n/r). We believe that results of that kind extend the applicability of exact algorithms for NP-hard problems. (C) 2009 Elsevier B.V. All rights reserved.

关键词： exponential-time algorithms Approximation algorithms Set-cover Instance reduction Trade-off

来源：评论

学校读者我要写书评

暂无评论

Optimal Polynomial-time Compression for Boolean Max CSP

引用

ACM TRANSACTIONS ON COMPUTATION THEORY 2024年第1期16卷 1-20页

作者： Jansen, Bart M. P. Wlodarczyk, Michal Eindhoven Univ Technol POB 513 NL-5600 MB Eindhoven MB Netherlands

In the Boolean maximum constraint satisfaction problem-Max CSP(G)-one is given a collection of weighted applications of constraints from a finite constraint language Gamma, over a common set of variables, and the goal is to assign Boolean values to the variables so that the total weight of satisfied constraints is maximized. There exists a concise dichotomy theorem providing a criterion on Gamma for the problem to be polynomial-time solvable and stating that otherwise, it becomes NP-hard. We study the NP-hard cases through the lens of kernelization and provide a complete characterization of Max CSP( Gamma) with respect to the optimal compression size. Namely, we prove that Max CSP(Gamma) parameterized by the number of variables n is either polynomial-time solvable, or there exists an integer d >= 2 depending on Gamma, such that: (1) An instance of Max CSP( Gamma) can be compressed into an equivalent instance with O(n(d) logn) bits in polynomial time, (2) Max CSP(Gamma) does not admit such a compression to O(n(d-epsilon)) bits unless NP subset of co-NP/poly. Our reductions are based on interpreting constraints as multilinear polynomials combined with the framework of "constraint implementations", formerly used in the context of APX-hardness. As another application of our reductions, we reveal tight connections between optimal running times for solving Max CSP(Gamma). More precisely, we show that obtaining a running time of the form O(2((1-epsilon)n)) for particular classes of Max CSPs is as hard as breaching this barrier for Max d-SAT for some d.

关键词： Constraint satisfaction problem kernelization exponential-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Improved Randomized algorithms for 3-SAT

Improved Randomized Algorithms for 3-SAT

引用

21st Annual International Symposium on algorithms and Computations (ISAAC)

作者： Iwama, Kazuo Seto, Kazuhisa Takai, Tadashi Tamaki, Suguru Kyoto Univ Sakyo Ku Kyoto 6068501 Japan East Japan Railway Co Tokyo Japan

ISBN: (纸本)9783642175169

This pager gives a new randomized algorithm which solves 3-SAT in time O(1.32113(n)). The previous best bound is O(1.32216(n)) due to Rolf (J. SAT, 2006). The new algorithm uses the same approach as Iwama and Tamaki (SODA 2004), but exploits the non-uniform initial assignment clue to Hofmeister et al. (STACS 2002) against the Schoning's local search (FOCS 1999).

关键词： 3-SAT exponential-time algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：