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

Fast exact algorithms for the SAT problem with bounded occurrences of variables

THEORETICAL COMPUTER SCIENCE 2025年 1029卷

作者： Peng, Junqiang Xiao, Mingyu Univ Elect Sci & Technol China Sch Comp Sci & Engn Chnegdu Peoples R China

We present fast algorithms for the general CNF satisfiability problem (SAT) with running-time bound O*(cd degrees), where cd is a function of the maximum occurrence d of variables (d can also be the average occurrence when each variable appears at least twice), and degrees is the number of variables in the input formula. Similar to SAT with bounded clause lengths, SAT with bounded occurrences of variables has also been extensively studied in the literature. Especially, the running-time bounds for small values of d, such as d = 3 and d = 4, have become bottlenecks for algorithms evaluated by the formula length L and other algorithms. In this paper, we show that SAT can be solved in time O*(1.1238 degrees) ford = 3 and O*(1.2628 degrees) ford = 4, improving the previous results O*(1.1279 degrees) and O*(1.2721 degrees) obtained by Wahlstr & ouml;m (SAT 2005) nearly 20 years ago. For d >= 5, we obtain a running time bound of O*(1.0641d degrees), implying a bound of O*(1.0641L) with respect to the formula length L.

关键词： Satisfiability exact algorithms Measure-and-conquer Amortized analysis Worst-case analysis

来源：评论

学校读者我要写书评

暂无评论

exact and parameterized algorithms for the independent cutset problem

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2025年 148卷

作者： Rauch, Johannes Rautenbach, Dieter Souza, Ueverton S. Ulm Univ Inst Optimizat & Operat Res Ulm Germany Univ Fed Fluminense Inst Computacao Niteroi Brazil

The INDEPENDENT CUTSET problem asks whether there is a set of vertices in a given graph that is both independent and a cutset. This problem is NP-complete even when the input graph is planar and has maximum degree five. We first present a O & lowast;(1.4423n)time algorithm to compute a minimum independent cutset (if any). Since the property of having an independent cutset is MSO1-expressible, our main results are concerned with structural parameterizations for the problem considering parameters incomparable with clique-width. We present FPT-time algorithms under the following parameters: the dual of the maximum degree, the dual of the solution size, the size of a dominating set (where a dominating set is given as an additional input), the size of an odd cycle transversal, the distance to chordal graphs, and the distance to P5-free graphs. We close by introducing the notion of alpha-domination, which generalizes key ideas of this article. (c) 2024 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： exact algorithms Parameterized algorithms Independent cutset

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for Maximum Induced Matching

引用

INFORMATION AND COMPUTATION 2017年 256卷 196-211页

作者： Xiao, Mingyu Tan, Huan Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 611731 Sichuan Peoples R China Univ Elect Sci & Technol China Chengdu 611731 Sichuan Peoples R China

This paper studies exact algorithms for the MAXIMUM INDUCED MATCHING problem, in which an n-vertex graph is given and we are asked to find a set of maximum number of edges in the graph such that no pair of edges in the set have a common endpoint or are adjacent by another edge. This problem has applications in many different areas. We give several structural properties of the problem and show that the problem can be solved in O*(1.4231(n)) time and polynomial space or O*(1.3752(n)) time and exponential space. (C) 2017 Elsevier Inc. All rights reserved.

关键词： exact algorithms Graph algorithms Maximum induced matching

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for Edge Domination

引用

ALGORITHMICA 2012年第4期64卷 535-563页

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

An edge dominating set in a graph G=(V,E) is a subset of the edges DaS dagger E such that every edge in E is adjacent or equal to some edge in D. The problem of finding an edge dominating set of minimum cardinality is NP-hard. We present a faster exact exponential time algorithm for this problem. Our algorithm uses O(1.3226 (n) ) time and polynomial space. The algorithm combines an enumeration approach of minimal vertex covers in the input graph 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 stepwisely. In each of these refinement steps, the worst cases in the measure and conquer analysis of the current algorithm are reconsidered and a new branching strategy is proposed on one of these worst cases. In this way a series of algorithms appears, each one slightly faster than the previous one, ending in the O(1.3226 (n) ) time algorithm. For each algorithm in the series, we also give a lower bound on its running time. We also show that the related problems: minimum weight edge dominating set, minimum maximal matching and minimum weight maximal matching can be solved in O(1.3226 (n) ) time and polynomial space using modifications of the algorithm for edge dominating set. In addition, we consider the matrix dominating set problem which we solve in O(1.3226 (n+m) ) time and polynomial space for nxm matrices, and the parametrised minimum weight maximal matching problem for which we obtain an O (au)(2.4179 (k) ) time and space algorithm.

关键词： Edge dominating set Minimum maximal matching exact algorithms Exponential time algorithms Measure and conquer

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for exact satisfiability and number of perfect matchings

引用

ALGORITHMICA 2008年第2期52卷 226-249页

作者： Bjorklund, Andreas Husfeldt, Thore Lund Univ Dept Comp Sci S-22100 Lund Sweden

We present exact algorithms with exponential running times for variants of n-element set cover problems, based on divide-and-conquer and on inclusion exclusion characterizations. We show that the exact Satisfiability problem of size l with m clauses can be solved in time 2(m)l(O(1)) and polynomial space. The same bounds hold for counting the number of solutions. As a special case, we can count the number of perfect matchings in an n-vertex graph in time 2(n)n(O(1)) and polynomial space. We also show how to count the number of perfect matchings in time O(1.732(n)) and exponential space. We give a number of examples where the running time can be further improved if the hypergraph corresponding to the set cover instance has low pathwidth. This yields exponential-time algorithms for counting k-dimensional matchings, exact Uniform Set Cover, Clique Partition, and Minimum Dominating Set in graphs of degree at most three. We extend the analysis to a number of related problems such as TSP and Chromatic Number.

关键词： exact algorithms set cover set partition exact satisfability number of perfect matchings

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for Minimum Weighted Dominating Induced Matching

引用

ALGORITHMICA 2017年第3期77卷 642-660页

作者： Lin, Min Chih Mizrahi, Michel J. Szwarcfiter, Jayme L. Consejo Nacl Invest Cient & Tecn Inst Calculo Buenos Aires DF Argentina Univ Buenos Aires Dept Comp Buenos Aires DF Argentina Univ Fed Rio de Janeiro Inst Mat COPPE Rio De Janeiro Brazil Univ Fed Rio de Janeiro NCE Rio De Janeiro Brazil Inst Nacl Metrol Qualidade & Tecnol Rio De Janeiro Brazil

Say that an edge of a graph G dominates itself and every other edge sharing a vertex of it. An edge dominating set of a graph is a subset of edges which dominates all edges of G. In particular, if every edge of G is dominated by exactly one edge of then is a dominating induced matching. It is known that not every graph admits a dominating induced matching, while the problem to decide if it does admit it is NP-complete. In this paper we consider the problems of counting the number of dominating induced matchings and finding a minimum weighted dominating induced matching, if any, of a graph with weighted edges. We describe three exact algorithms for general graphs. The first runs in linear time for a given vertex dominating set of fixed size of the graph. The second runs in polynomial time if the graph admits a polynomial number of maximal independent sets. The third one is an time and polynomial (linear) space, which improves over the existing algorithms for exactly solving this problem in general graphs.

关键词： exact algorithms Graph theory Dominating induced matchings

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for single-machine scheduling problems with a variable maintenance

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2016年第0期98卷 427-433页

作者： Ying, Kuo-Ching Lu, Chung-Cheng Chen, Jhao-Cheng Natl Taipei Univ Technol Dept Ind Engn & Management Taipei Taiwan Natl Chiao Tung Univ Dept Transportat & Logist Management Hsinchu Taiwan

This paper deals with four single-machine scheduling problems (SMSPs) with a variable machine maintenance. The objectives of the four SMSPs are to minimize mean lateness, maximum tardiness, total flow time and mean tardiness, respectively. These four SMSPs are important in the literature and in practice. This study proposes an exact algorithm with the computational complexity O(n(2)) for each of the four SMSPs. In addition to the given jobs, the machine maintenance activity between two consecutive jobs is optimally scheduled. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Scheduling Variable maintenance exact algorithms

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for Intervalizing Coloured Graphs

引用

THEORY OF COMPUTING SYSTEMS 2016年第2期58卷 273-286页

作者： Bodlaender, Hans L. van Rooij, Johan M. M. Univ Utrecht Dept Informat & Comp Sci POB 80-089 NL-3508 TB Utrecht Netherlands Eindhoven Univ Technol Dept Math & Comp Sci POB 513 NL-5600 MB Eindhoven Netherlands Consultants Qualitat Methods POB 414 NL-5600 AK Eindhoven Netherlands

In the INTERVALIZING COLOURED GRAPHS problem, one must decide for a given graph G = (V, E) with a proper vertex colouring of G whether G is the subgraph of a properly coloured interval graph. For the case that the number of colors is fixed, we give an exact algorithm that uses 2(O(n/log n)) time. We also give an O*(2(n)) algorithm for the case that the number of colors is not fixed.

关键词： Graph algorithms exact algorithms Interval graphs Subexponential time Intervalizing coloured graphs Pathwidth

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for the Equitable Traveling Salesman Problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2017年第2期261卷 475-485页

作者： Kinable, Joris Smeulders, Bart Delcour, Eline Spieksma, Frits C. R. Carnegie Mellon Univ Robot Inst 5000 Forbes Ave Pittsburgh PA 15213 USA Carnegie Mellon Univ Tepper Sch Business 5000 Forbes Ave Pittsburgh PA 15213 USA Katholieke Univ Leuven Dept Comp Sci CODeS Gebroeders De Smetstr 1 B-9000 Ghent Belgium Katholieke Univ Leuven IMinds ITEC Gebroeders De Smetstr 1 B-9000 Ghent Belgium Univ Liege HEC Management Sch QuantOM Rue Louvrex 14 B-4000 Liege Belgium Barry Callebaut Aalstersestr 122 B-9280 Lebbeke Belgium Katholieke Univ Leuven Fac Business & Econ ORSTAT Naamsestr 69 B-3000 Leuven Belgium

Given a weighted graph G = (V, E), the Equitable Traveling Salesman Problem (ETSP) asks for two perfect matchings in G such that (1) the two matchings together form a Hamiltonian cycle in G and (2) the absolute difference in costs between the two matchings is minimized. The problem is shown to be NP Hard, even when the graph G is complete. We present two integer programming models to solve the ETSP problem and compare the strength of these formulations. One model is solved through branch-and cut, whereas the other model is solved through a branch-and-price framework. A simple local search heuristic is also implemented. We conduct computational experiments on different types of instances, often derived from the TSPLib. It turns out that the behavior of the different approaches varies with the type of instances. For small and medium sized instances, branch-and-bound and branch-and-price produce comparable results. However, for larger instances branch-and-bound outperforms branch-and price. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization Traveling Salesman Problem Branch-and-bound Branch-and-price exact algorithms

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for scheduling programs with shared tasks

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第5期43卷 1602-1627页

作者： Kacem, Imed Lucarelli, Giorgio Naze, Theo Univ Lorraine LCOMS Metz France

We study a scheduling problem where the jobs we have to perform are composed of one or more tasks. If two jobs sharing a non-empty subset of tasks are scheduled on the same machine, then these shared tasks have to be performed only once. This kind of problem is known in the literature under the names of VM-PACKING or PAGINATION. Our objective is to schedule a set of these objects on two parallel identical machines, with the aim of minimizing the makespan. This problem is NP-complete as an extension of the PARTITION problem. In this paper we present three exact algorithms with worst-case time-complexity guarantees, by exploring different branching techniques. Our first algorithm focuses on the relation between jobs sharing one or more symbols in common, whereas the two other algorithms branches on the shared symbols.

关键词： Scheduling exact algorithms Makespan minimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：