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

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS 2013年第3期47卷 235-240页

作者： Krzywkowski, Marcin Gdansk Univ Technol Fac Elect Telecommun & Informat PL-80233 Gdansk Poland

We provide an algorithm for listing all minimal 2-dominating sets of a tree of order n in time O(1.3248(n)). This implies that every tree has at most 1.3248(n) minimal 2-dominating sets. We also show that this bound i... 详细信息

关键词： Domination 2-domination minimal 2-dominating set tree counting exact exponential algorithm listing algorithm

来源：评论

学校读者我要写书评

暂无评论

Computing Directed Pathwidth in O(1.89ⁿ) Time

引用

algorithmICA 2016年第1期75卷 138-157页

作者： Kitsunai, Kenta Kobayashi, Yasuaki Komuro, Keita Tamaki, Hisao Tano, Toshihiro Meiji Univ Dept Comp Sci Kawasaki Kanagawa Japan Gakushuin Univ Ctr Comp Toshima Ku Tokyo 171 Japan

We give an algorithm for computing the directed pathwidth of a digraph with n vertices in O(1.89(n)) time. This is the first algorithm with running time better than the straightforward O*(2(n)). As a special case, it computes the pathwidth of an undirected graph in the same amount of time, improving on the algorithm due to Suchan and Villanger which runs in O(1.9657(n)) time.

关键词： exact exponential algorithm Graph algorithm Pathwidth

来源：评论

学校读者我要写书评

暂无评论

Pathwidth of cubic graphs and exact algorithms

引用

INFORMATION PROCESSING LETTERS 2006年第5期97卷 191-196页

作者： Fomin, FV Hoie, K Univ Bergen Dept Informat N-5020 Bergen Norway

We prove that for any epsilon > 0 there exists an integer n(epsilon) such that the pathwidth of every cubic (or 3-regular) graph on n > n(epsilon) vertices is at most (1/6 + epsilon)n. Based on this bound we improve the worst case time analysis for a number of exact exponential algorithms on graphs of maximum vertex degree three. (c) 2005 Elsevier B.V. All rights reserved.

关键词： treewidth pathwidth cubic graph exact exponential algorithm maximum independent set max-cut minimum dominating set graph algorithms

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for TSP in Degree-3 Graphs Via Circuit Procedure and Amortization on Connectivity Structure

引用

algorithmICA 2016年第2期74卷 713-741页

作者： Xiao, Mingyu Nagamochi, Hiroshi Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 610054 Peoples R China Kyoto Univ Dept Appl Math & Phys Grad Sch Informat Kyoto 606 Japan

The paper presents an -time and polynomial-space algorithm for the traveling salesman problem in an -vertex graph with maximum degree 3. This improves all previous time bounds of polynomial-space algorithms for this problem. Our algorithm is a simple branch-and-search algorithm with only one branch rule designed on a cut-circuit structure of a graph induced by unprocessed edges. To improve a time bound by a simple analysis on measure and conquer, we introduce an amortization scheme over the cut-circuit structure by defining the measure of an instance to be the sum of not only weights of vertices but also weights of connected components of the induced graph.

关键词： Traveling salesman problem exact exponential algorithm Graph algorithm Connectivity Measure and conquer

来源：评论

学校读者我要写书评

暂无评论

Inclusion/Exclusion Meets Measure and Conquer

引用

algorithmICA 2014年第3期69卷 685-740页

作者： Nederlof, Jesper van Rooij, Johan M. M. van Dijk, Thomas C. Univ Utrecht Dept Informat & Comp Sci NL-3584 CC Utrecht Netherlands Consultants Quantitat Methods NL-5616 RM Eindhoven Netherlands Univ Wurzburg Lehrstuhl Informat 1 D-97070 Wurzburg Germany

Inclusion/exclusion and measure and conquer are two central techniques from the field of exact exponential-time algorithms that recently received a lot of attention. In this paper, we show that both techniques can be used in a single algorithm. This is done by looking at the principle of inclusion/exclusion as a branching rule. This inclusion/exclusion-based branching rule can be combined in a branch-and-reduce algorithm with traditional branching rules and reduction rules. The resulting algorithms can be analysed using measure and conquer allowing us to obtain good upper bounds on their running times. In this way, we obtain the currently fastest exact exponential-time algorithms for a number of domination problems in graphs. Among these are faster polynomial-space and exponential-space algorithms for #Dominating Set and Minimum Weight Dominating Set (for the case where the set of possible weight sums is polynomially bounded), and a faster polynomial-space algorithm for Domatic Number. This approach is also extended in this paper to the setting where not all requirements in a problem need to be satisfied. This results in faster polynomial-space and exponential-space algorithms for Partial Dominating Set, and faster polynomial-space and exponential-space algorithms for the well-studied parameterised problem k-Set Splitting and its generalisation k-Not-All-Equal Satisfiability.

关键词： exact exponential algorithm Dominating set NP-hard Branching Inclusion/Exclusion

来源：评论

学校读者我要写书评

暂无评论

The Stable Roommates Problem with Unranked Entries

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2018年第9期E101A卷 1412-1419页

作者： Suto, Hiroaki Shurbevski, Aleksandar Nagamochi, Hiroshi Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto 6068501 Japan

The family of stable matching problems have been well-studied across a wide field of research areas, including economics, mathematics and computer science. In general, an instance of a stable matching problem is given by a set of participants who have expressed their preferences of each other, and asks to find a "stable" matching, that is, a pairing of the participants such that no unpaired participants prefer each other to their assigned partners. In the case of the Stable Roommates Problem (SR), it is known that given an even number n of participants, there might not exist a stable matching that pairs all of the participants, but there exist efficient algorithms to determine if this is possible or not, and if it is possible, produce such a matching. Common extensions of SR allow for the participants' preference lists to be incomplete, or include indifference. Allowing indifference in turn, gives rise to different possible definitions of stability, super, strong, and weak stability. While instances asking for super and strongly stable matching can be efficiently solved even if preference lists are incomplete, the case of weak stability is NP-complete. We examine a restricted case of indifference, introducing the concept of unranked entries. For this type of instances, we show that the problem of finding a weakly stable matching remains NP-complete even if each participant has a complete preference list with at most two unranked entries, or is herself unranked for up to three other participants. On the other hand, for instances where there are m acceptable pairs and there are in total k unranked entries in all of the participants' preference lists, we propose an O(2(k)n(2))-time and polynomial space algorithm that finds a stable matching, or determines that none exists in the given instance.

关键词： stable matching indifference NP-hardness exact exponential algorithm

来源：评论

学校读者我要写书评

暂无评论

A Satisfiability algorithm for Synchronous Boolean Circuits

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2021年第3期E104D卷 392-393页

作者： Morizumi, Hiroki Shimane Univ Matsue Shimane 6908504 Japan

The circuit satisfiability problem has been intensively studied since Ryan Williams showed a connection between the problem and lower bounds for circuit complexity. In this letter, we present a #SAT algorithm for sync... 详细信息

关键词： circuit satisfiability problem synchronous circuit exact exponential algorithm circuit complexity

来源：评论

学校读者我要写书评

暂无评论

Minimal Double Dominating Sets in Trees

Minimal Double Dominating Sets in Trees

引用

8th International Frontiers of algorithmics Workshop (FAW)

作者： Krzywkowski, Marcin Univ Johannesburg Dept Math Johannesburg South Africa

We provide an algorithm for listing all minimal double dominating sets of a tree of order n in time O(1.3248(n)). This implies that every tree has at most 1.3248(n) minimal double dominating sets. We also show that th... 详细信息

ISBN: (纸本)9783319080161;9783319080154

关键词： domination double domination minimal double dominating set tree combinatorial bound exact exponential algorithm listing algorithm

来源：评论

学校读者我要写书评

暂无评论

A Polynomial-Space exact algorithm for TSP in Degree-6 Graphs 18th

A Polynomial-Space Exact Algorithm for TSP in Degree-6 Graph...

引用

18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCG2)

作者： Yunos, Norhazwani Md Shurbevski, Aleksandar Nagamochi, Hiroshi Kyoto Univ Dept Appl Math & Phys Kyoto Japan Tech Univ Malaysia Malacca Durian Tunggal Malacca Malaysia

ISBN: (纸本)9783319485324;9783319485317

This paper presents the first polynomial-space exact algorithm specialized for the TSP in graphs with degree at most 6. We develop a set of branching rules to aid the analysis of the branching algorithm. Using the measure-and-conquer method, we show that when applied to an n-vertex graph with degree at most 6, the algorithm has a running time of O*(3.0335(n)), which is still advantageous over other known polynomial-space algorithms for the TSP in general graphs.

关键词： Traveling salesman problem exact exponential algorithm Branch-and-Reduce Measure-and-Conquer

来源：评论

学校读者我要写书评

暂无评论

Finding a minimum feedback vertex set in time O(1.7548ⁿ)

引用

2nd International Workshop on Parameterized and exact Computation

作者： Fomin, Fedor V. Gaspers, Serge Pyatkin, Artem V. Univ Bergen Dept Informat N-5020 Bergen Norway

ISBN: (纸本)3540390987

The problem of finding a minimum feedback vertex set has many applications and its history can be traced back to the early '60s (see the survey of Festa at al. [2]). It is also one of the classical NP-complete problems from Karp's list [5]. There is quite a dramatic story of obtaining faster and faster parameterized algorithms with a chain of improvements (see e.g. [7]) concluding with 2(O(k))n(O(1))-time algorithms obtained independently by different research groups [1,4]. A feedback vertex set of a graph on n vertices can be trivially found in time 0(2 n n) by trying all possible vertex subsets. For a long time, despite attacks of many researchers, no faster exponential time algorithm was known. Very recently Razgon [8] broke the 2(n) barrier with an O(1.8899(n)) time algorithm. The algorithm of Razgon is based on the Branch & Reduce paradigm and its analysis is nice and clever. In this paper we show how to find a minimum feedback vertex set in time O(1.7548(n)). Our improvement is based on Razgon's idea of measuring the progress of the branching algorithm. The most significant improvement in the running time of our algorithm is due to a new branching rule which is based on Proposition 2. This rule works nicely except one case, which, luckily, can be reduced to finding an independent set of maximum size.

关键词： minimum feedback vertex set maximum induced forest exact exponential algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：