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

Improved parameterized algorithms and kernels for mixed domination

THEORETICAL COMPUTER SCIENCE 2020年 815卷 109-120页

作者： Xiao, Mingyu Sheng, Zimo Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Peoples R China

A mixed domination of a graph G =(V, E) is a mixed set Dof vertices and edges such that for every edge or vertex, if it is not in D, then it is adjacent or incident to at least one vertex or edge in D. TheMixed Dominationproblem is to check whether there is a mixed domination of size at most kin a graph. Mixed domination is a mixture concept of vertex domination and edge domination, and the mixed domination problem has been studied from the view of approximation algorithms, parameterized algorithms, and so on. In this paper, we give a branch-and-search algorithm with running time bound of O*(4.172k), which improves the previous bound of O* (7.465k). For kernelization, it is known that the problem parameterized by kin general graphs is unlikely to have a polynomial kernel. We show the problem in planar graphs allows linear kernel by giving a kernel of 11k - 16 vertices. (C) 2020 Elsevier B.V. All rights reserved.

关键词： parameterized algorithms Mixed domination Graph algorithms Kernelization Branch-and-search

来源：评论

学校读者我要写书评

暂无评论

Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees

引用

THEORETICAL COMPUTER SCIENCE 2013年 470卷 10-22页

作者： Akutsu, Tatsuya Fukagawa, Daiji Halldorsson, Magnus M. Takasu, Atsuhiro Tanaka, Keisuke Kyoto Univ Bioinformat Ctr Inst Chem Res Kyoto 6110011 Japan Doshisha Univ Fac Culture & Informat Sci Kyoto 6100394 Japan Reykjavik Univ ICE TCS Sch Comp Sci IS-101 Reykjavik Iceland Natl Inst Informat Tokyo 1018430 Japan Tokyo Inst Technol Dept Math & Comp Sci Tokyo 152 Japan

Given two rooted, labeled, unordered trees, the common subtree problem is to find a bijective matching between subsets of nodes of the trees of maximum cardinality which preserves labels and ancestry relationship. The tree edit distance problem is to determine the least cost sequence of insertions, deletions and substitutions that converts a tree into another given tree. Both problems are known to be hard to approximate within some constant factor in general. We tackle these problems from two perspectives: giving exact algorithms, either for special cases or in terms of some parameters;and approximation algorithms and hardness of approximation. We present a parameterized algorithm in terms of the number of branching nodes that solves both problems and yields polynomial algorithms for several special classes of trees. This is complemented with a tighter APX-hardness proof that holds when the trees are of height one and two, respectively. Furthermore, we present the first approximation algorithms for both problems. In particular, for the common subtree problem for t trees, we present an algorithm achieving at log(2) (b(OPT) + 1) ratio, where b(OPT) is the number of branching nodes in the optimal solution. We also present constant factor approximation algorithms for both problems in the case of bounded height trees. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Tree edit distance Approximation algorithms parameterized algorithms Dynamic programming Unordered trees

来源：评论

学校读者我要写书评

暂无评论

An overview of techniques for designing parameterized algorithms

引用

COMPUTER JOURNAL 2008年第1期51卷 122-136页

作者： Sloper, Christian Telle, Jan Arne Univ Bergen Dept Informat N-5008 Bergen Norway

A survey of the most important and general techniques in parameterized algorithm design is given. Each technique is explained with a meta-algorithm, its use is illustrated by examples, and it is placed in a taxonomy u... 详细信息

关键词： parameterized algorithms fixed-parameter tractability

来源：评论

学校读者我要写书评

暂无评论

Discriminantal subset convolution: Refining exterior-algebraic methods for parameterized algorithms

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2022年 129卷 62-71页

作者： Brand, Cornelius Vienna Univ Technol Algorithms & Complex Grp Vienna Austria

We give a simplified account of the recent algebraic methods obtained for the longest path problem of Brand, Dell and Husfeldt (STOC'18) and Brand (ESA'19). To this end, we introduce a new kind of subset convolution, discriminantal subset convolution, which we motivate as a distillate of exterior-algebraic operations. The algorithm in the new presentation achieves the almost competitive bound of 2.619k center dot poly(n), first achieved by Fomin et al. (2016) [8], for deterministically finding paths of length k, while it allows for the same running time for the k-internal out-branching problem, improving upon Brand (ESA'19) and reproducing the state-of-the-art of Brand and Pratt (ICALP'21). (c) 2022 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： parameterized algorithms Algebraic algorithms Longest path problem Extensor coding Fast subset convolution

来源：评论

学校读者我要写书评

暂无评论

Complexity and parameterized algorithms for Cograph Editing

引用

THEORETICAL COMPUTER SCIENCE 2012年 461卷 45-54页

作者： Liu, Yunlong Wang, Jianxin Guo, Jiong Chen, Jianer Cent South Univ Sch Informat Sci & Engn Changsha 410083 Hunan Peoples R China Hunan Normal Univ Sch Math & Comp Sci Changsha 410013 Hunan Peoples R China Univ Saarland D-66123 Saarbrucken Germany Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA

Cograph Editing is to find for a given graph G = (V, E) a set of at most k edge additions and deletions that transform G into a cograph. The computational complexity of this problem was open in the past. In this paper, we first show that this problem is NP-hard by a reduction from Exact 3-Cover. Subsequently, we present a parameterized algorithm based on a refined search tree technique with a running time of O(4.612(k) + vertical bar V vertical bar(4.5)), which improves the trivial algorithm of running time O(6(k) + vertical bar V vertical bar(4-5)). (c) 2011 Elsevier B.V. All rights reserved.

关键词： Cograph Editing NP-hardness parameterized algorithms P-4-sparse graph

来源：评论

学校读者我要写书评

暂无评论

Faster parameterized algorithms for Minimum Fill-in

引用

19th Annual International Symposium on algorithms and Computation (ISAAC)

作者： Bodlaender, Hans L. Heggernes, Pinar Villanger, Yngve Univ Bergen Dept Informat N-5020 Bergen Norway Univ Utrecht Dept Informat & Comp Sci NL-3508 TB Utrecht Netherlands

ISBN: (纸本)3540921818

We present two parameterized algorithms for the MINIMUM FILL-IN problem, also known as CHORDAL COMPLETION: given an arbitrary graph G and integer k, can we add at most k edges to G to obtain a chordal graph? Our first algorithm has running time O(k(2)nm + 3.0793(k)), and requires polynomial space. This improves the base of the exponential part of the best known parameterized algorithm time for this problem so far. We are able to improve this running time even further, at the cost of more space. Our second algorithm has running time O(k(2)nm + 2.35965(k)) and requires O*(1.7549(k)) space. To achieve these results, we present a new lemma describing the edges that can safely be added to achieve a chordal completion with the minimum number of edges, regardless of k.

关键词： Minimum Fill-in parameterized algorithms Chordal graphs Fixed parameter tractability

来源：评论

学校读者我要写书评

暂无评论

Exact and parameterized algorithms for the Independent Cutset Problem 24th

Exact and Parameterized Algorithms for the Independent Cutse...

引用

24th International Symposium on Fundamentals of Computation Theory (FCT)

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

ISBN: (纸本)9783031435867;9783031435874

The Independent Cutset problem asks whether there is a set of vertices in a given graph that is both independent and a cutset. Such a problem is NP-complete even when the input graph is planar and has maximum degree five. In this paper, we first present a O* (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 for the problem considering 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 a-domination, which allows us to identify more fixed-parameter tractable and polynomial-time solvable cases.

关键词： exact algorithms parameterized algorithms independent cutset

来源：评论

学校读者我要写书评

暂无评论

On subexponential parameterized algorithms for Steiner Tree and Directed Subset TSP on planar graphs 59

On subexponential parameterized algorithms for Steiner Tree ...

引用

59th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Marx, Daniel Pilipczuk, Marcin Pilipczuk, Michal Hungarian Acad Sci MTA SZTAKI Inst Comp Sci & Control Budapest Hungary Univ Warsaw Inst Informat Warsaw Poland

ISBN: (纸本)9781538642306

There are numerous examples of the so-called "square root phenomenon" in the field of parameterized algorithms: many of the most fundamental graph problems, parameterized by some natural parameter k, become significantly simpler when restricted to planar graphs and in particular the best possible running time is exponential in O(root k) instead of O(k) (modulo standard complexity assumptions). We consider two classic optimization problems parameterized by the number of terminals. The STEINER TREE problem asks for a minimum-weight tree connecting a given set of terminals T in an edge-weighted graph. In the SUBSET TRAVELING SALESMAN problem we are asked to visit all the terminals T by a minimum-weight closed walk. We investigate the parameterized complexity of these problems in planar graphs, where the number k - vertical bar T vertical bar of terminals is regarded as the parameter. Our results are the following: SUBSET TSP can be solved in time 2(O(root k log k)).n(O(1)) even on edge-weighted directed planar graphs. This improves upon the algorithm of Klein and Marx [SODA 2014] with the same running time that worked only on undirected planar graphs with polynomially large integer weights. Assuming the Exponential-Time Hypothesis, STEINER TREE on undirected planar graphs cannot be solved in time 2(o(k)).n(O(1)), even in the unit-weight setting. This lower bound makes STEINER TREE the first "genuinely planar" problem (i.e., where the input is only planar graph with a set of distinguished terminals) for which we can show that the square root phenomenon does not appear. STEINER TREE can be solved in time n(O(root k)).W on undirected planar graphs with maximum edge weight W. Note that this result is incomparable to the fact that the problem is known to be solvable in time 2(k).n(O(1)) even in general graphs. A direct corollary of the combination of our results for STEINER TREE is that this problem does not admit a parameter-preserving polynomial kernel on planar graphs un

关键词： Steiner tree subexponential algorithms parameterized algorithms planar graphs

来源：评论

学校读者我要写书评

暂无评论

Improved parameterized algorithms for Mixed Domination 13th

Improved Parameterized Algorithms for Mixed Domination

引用

13th International Conference on Algorithmic Aspects in Information and Management (AAIM)

作者： Xiao, Mingyu Sheng, Zimo Univ Elect Sci & Technol China Chengdu Peoples R China

ISBN: (纸本)9783030271954;9783030271947

A mixed domination of a graph G = (V, E) is a mixed set D of vertices and edges such that for every edge or vertex, if it is not in D, then it is adjacent or incident to at least one vertex or edge in D. The Mixed Domination problem is to check whether there is a mixed domination of size at most k in a graph. Mixed domination is a mixture concept of vertex domination and edge domination, and the mixed domination problem has been studied from the view of approximation algorithms, parameterized algorithms, and so on. In this paper, we give a branch-and-search algorithm with running time bound of O* (4.172(k)), which improves the previous bound of O* (7.465(k)). For kernelization, it is known that the problem parameterized by k in general graphs is unlikely to have a polynomial kernel. We show the problem in planar graphs allows linear kernels by giving a kernel of 11k vertices.

关键词： parameterized algorithms Mixed Domination Graph algorithms Kernelization Branch-and-search

来源：评论

学校读者我要写书评

暂无评论

Exact and parameterized algorithms for Restricted Subset Feedback Vertex Set in Chordal Graphs 17th

Exact and Parameterized Algorithms for Restricted Subset Fee...

引用

17th Annual Conference on Theory and Applications of Models of Computation (TAMC)

作者： Bai, Tian Xiao, Mingyu Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Peoples R China

ISBN: (纸本)9783031203497;9783031203503

The Restricted Subset Feedback Vertex Set problem (R-SFVS) takes a graph G = (V, E), a terminal set T subset of V, and an integer k as the input. The task is to determine whether there exists a subset S subset of V \ T of at most k vertices, after deleting which no terminal in T is contained in a cycle in the remaining graph. R-SFVS is NP-complete even when the input graph is restricted to chordal graphs. In this paper, we show that R-SFVS in chordal graphs can be solved in time O(1.1550 vertical bar V vertical bar), significantly improving all the previous results. As a by-product, we prove that the Maximum Independent Set problem parameterized by the edge clique cover number is fixed-parameter tractable. Furthermore, by using a simple reduction from R-SFVS to Vertex Cover, we obtain a 1.2738(k)vertical bar V vertical bar(O(1))-time parameterized algorithm and an O(k(2))-kernel for R-SFVS in chordal graphs.

关键词： Subset feedback vertex set Chordal graphs Exact exponential algorithms parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：