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

A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2018年 97卷 121-146页

作者： Eiben, Eduard Ganian, Robert Kwon, O-joung Univ Bergen Dept Informat Bergen Norway TU Wien Algorithms & Complex Grp Vienna Austria Incheon Natl Univ Dept Math 119 Acad Ro Incheon South Korea

Vertex deletion problems ask whether it is possible to delete at most k vertices from a graph so that the resulting graph belongs to a specified graph class. Over the past years, the parameterized complexity of vertex deletion to a plethora of graph classes has been systematically researched. Here we present the first single-exponential fixed-parameter tractable algorithm for vertex deletion to distance-hereditary graphs, a well-studied graph class which is particularly important in the context of vertex deletion due to its connection to the graph parameter rank-width. We complement our result with matching asymptotic lower bounds based on the exponential time hypothesis. As an application of our algorithm, we show that a vertex deletion set to distance-hereditary graphs can be used as a parameter which allows single-exponential fixed-parameter tractable algorithms for classical NP-hard problems. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Distance-hereditary graphs fixed-parameter algorithms Rank-width

来源：评论

学校读者我要写书评

暂无评论

Almost 2-SAT is fixed-parameter tractable

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2009年第8期75卷 435-450页

作者： Razgon, Igor O'Sullivan, Barry Univ Coll Cork Dept Comp Sci Cork Constraint Computat Ctr Cork Ireland

We consider the following problem. Given a 2-CNF formula, is it possible to remove at most k clauses so that the resulting 2-CNF formula is satisfiable? This problem is known to different research communities in theoretical computer science under the names Almost 2-SAT, All-but-k 2-SAT, 2-CNF deletion, and 2-SAT deletion. The status of the fixed-parameter tractability of this problem is a long-standing open question in the area of parameterized complexity. We resolve this open question by proposing an algorithm that solves this problem in O(15(k), x k x m(3)) time showing that this problem is fixed-parameter tractable. (C) 2009 Elsevier Inc. All rights reserved.

关键词： fixed-parameter algorithms Satisfiability problems Separation problems

来源：评论

学校读者我要写书评

暂无评论

Constant ratio fixed-parameter approximation of the edge multicut problem

引用

INFORMATION PROCESSING LETTERS 2009年第20期109卷 1161-1166页

作者： Marx, Daniel Razgon, Igor Natl Univ Ireland Univ Coll Cork Cork Constraint Computat Ctr Cork Ireland Budapest Univ Technol & Econ Dept Comp Sci & Informat Theory Budapest Hungary

The input of the Edge Multicut problem consists of an undirected graph G and pairs of terminals {s(1), t(1)),...,{s(m), t(m));the task is to remove a minimum set of edges such that s(i) and t(i) are disconnected for every 1 <= i <= m. The parameterized complexity of the problem, parameterized by the maximum number k of edges that are allowed to be removed, is currently open. The main result of the paper is a parameterized 2-approximation algorithm: in time f (k).n(0(1)), we can either find a solution of size 2k or correctly conclude that there is no solution of size k. The proposed algorithm is based on a transformation of the Edge Multicut problem into a variant of the parameterized Max-2SAT problem, where the parameter is related to the number of clauses that are not satisfied. It follows from previous results that the latter problem can be 2-approximated in a fixed-parameter time: on the other hand, we show here that it is W[1]-hard. Thus the additional contribution of the present paper is introducing the first natural W[1]-hard problem that is constant-ratio fixed-parameter approximable. (c) 2009 Elsevier B.V. All rights reserved.

关键词： fixed-parameter algorithms parameterized approximation Multicut Satisfiability problems Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

FPT algorithms for path-transversal and cycle-transversal problems

引用

DISCRETE OPTIMIZATION 2011年第1期8卷 61-71页

作者： Guillemot, Sylvain Univ Paris Est Inst Gaspard Monge F-77454 Champs Sur Marne Marne La Vallee France

We study the parameterized complexity of several vertex- and edge-deletion problems on graphs, parameterized by the number p of deletions. The first kind of problems are separation problems on undirected graphs, where we aim at separating distinguished vertices in a graph. The second kind of problems are feedback set problems on group-labelled graphs, where we aim at breaking nonnull cycles in a graph having its arcs labelled by elements of a group. We obtain new FPT algorithms for these different problems, relying on a generic O*(4(p)) algorithm for breaking paths of a homogeneous path system. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Cut problems Feedback set problems Linear programming fixed-parameter algorithms

来源：评论

学校读者我要写书评

暂无评论

New analysis and computational study for the planar connected dominating set problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第1期32卷 198-225页

作者： Marzban, Marjan Gu, Qian-Ping Jia, Xiaohua Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China

The connected dominating set (CDS) problem is a well studied NP-hard problem with many important applications. Dorn et al. (Algorithmica 58:790-810 2010) introduce a branch-decomposition based algorithm design technique for NP-hard problems in planar graphs and give an algorithm (DPBF algorithm) which solves the planar CDS problem in time and time, with a conventional method and fast matrix multiplication in the dynamic programming step of the algorithm, respectively. We show that DPBF algorithm solves the planar CDS problem in time with a conventional method and in time with a fast matrix multiplication. For a graph , let be the branchwidth of and be the connected dominating number of . We prove . From this result, the planar CDS problem admits an time fixed-parameter algorithm. We report computational study results on the practical performance of DPBF algorithm, which show that the size of instances can be solved by the algorithm mainly depends on the branchwidth of the instances, coinciding with the theoretical analysis. For graphs with small or moderate branchwidth, the CDS problem instances with size up to a few thousands edges can be solved in a practical time and memory space.

关键词： Branch-decomposition based algorithms Connected dominating set Planar graphs fixed-parameter algorithms Computational study

来源：评论

学校读者我要写书评

暂无评论

An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems

引用

DISCRETE APPLIED MATHEMATICS 2015年 193卷 145-161页

作者： Komusiewicz, Christian Sorge, Manuel TU Inst Softwaretech & Theoret Informat Berlin Germany

We investigate the computational complexity of the DENSEST k-SUBGRAPH problem, where the input is an undirected graph G = (V, E) and one wants to find a subgraph on exactly k vertices with the maximum number of edges. We extend previous work on DENSEST k-SUBGRAPH by studying its parameterized complexity for parameters describing the sparseness of the input graph and for parameters related to the solution size k. On the positive side, we show that, when fixing some constant minimum density mu of the sought subgraph, DENSEST k-SUBGRAPH becomes fixed-parameter tractable with respect to either of the parameters maximum degree of G and h-index of G. Furthermore, we obtain a fixed-parameter algorithm for DENSEST k-SUBGRAPH with respect to the combined parameter "degeneracy of G and vertical bar V vertical bar - k". On the negative side, we find that DENSEST k-SUBGRAPH is W[1]-hard with respect to the combined parameter "solution size k and degeneracy of G". We furthermore strengthen a previous hardness result for DENSEST k-SUBGRAPH (Cai, 2008) by showing that for every fixed mu, 0 < mu < 1, the problem of deciding whether G contains a subgraph of density at least mu is W[1]-hard with respect to the parameter vertical bar V] - k. Our positive results are obtained by an algorithmic framework that can be applied to a wide range of fixed-CARDINALITY OPTIMIZATION problems. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Clique relaxations NP-hard problems fixed-parameter algorithms Subgraph enumeration

来源：评论

学校读者我要写书评

暂无评论

Simultaneous Identification of Duplications, Losses, and Lateral Gene Transfers

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2012年第5期9卷 1515-1528页

作者： Chen, Zhi-Zhong Deng, Fei Wang, Lusheng Tokyo Denki Univ Div Informat Syst Design Hatoyama Saitama 3590394 Japan City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China

We give a fixed-parameter algorithm for the problem of enumerating all minimum-cost LCA-reconciliations involving gene duplications, gene losses, and lateral gene transfers (LGTs) for a given species tree S and a given gene tree G. Our algorithm can work for the weighted version of the problem, where the costs of a gene duplication, a gene loss, and an LGT are left to the user's discretion. The algorithm runs in O(m + 3(k/c)n) time, where m is the number of vertices in S, n is the number of vertices in G, c is the smaller between a gene duplication cost and an LGT cost, and k is the minimum cost of an LCA-reconciliation between S and G. The time complexity is indeed better if the cost of a gene loss is greater than 0. In particular, when the cost of a gene loss is at least 0.614c, the running time of the algorithm is O(m + 2.78(k/c)n).

关键词： Phylogenetic trees reconciliations fixed-parameter algorithms

来源：评论

学校读者我要写书评

暂无评论

parameterized and approximation algorithms for finding two disjoint matchings

引用

THEORETICAL COMPUTER SCIENCE 2014年第0期556卷 85-93页

作者： Chen, Zhi-Zhong Fan, Ying Wang, Lusheng Tokyo Denki Univ Div Informat Syst Design Hatoyama Saitama 3500394 Japan City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China

We first present a randomized fixed-parameter algorithm for the NP-hard problem of deciding if there are two matchings M-1 and M-2 in a given graph G such that vertical bar M-1 vertical bar+ vertical bar M-2 vertical bar is a given number k. The algorithm runs in O (2(k)k(m + n)) expected time and can be derandomized to run in O (2(2k+12 log2 (2k)) kn (m + n) time, where n (respectively, m) is the number of vertices (respectively, edges) in G. We then extend the algorithm to the weighted version of the problem. We further present a combinatorial approximation algorithm for the NP-hard problem of finding two disjoint matchings in a given edge-weighted graph G so that their total weight is maximized. The algorithm achieves an approximation ratio close to 0.76 and runs in O(m + n(3) alpha(n)) time, where alpha is the inverse Ackermann function. (C) 2014 Elsevier B.V. All rights reserved.

关键词： fixed-parameter algorithms Approximation algorithms Color-coding Universal sets Matchings

来源：评论

学校读者我要写书评

暂无评论

THE UNIFORM MINIMUM-ONES 2SAT PROBLEM AND ITS APPLICATION TO HAPLOTYPE CLASSIFICATION

引用

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS 2010年第3期44卷 363-377页

作者： Boeckenhauer, Hans-Joachim Forisek, Michal Oravec, Jan Steffen, Bjoern Steinhoefel, Kathleen Steinova, Monika ETH Dept Comp Sci Zurich Switzerland Comenius Univ Dept Comp Sci Bratislava 81806 Slovakia Kings Coll London Dept Comp Sci London England

Analyzing genomic data for finding those gene variations which are responsible for hereditary diseases is one of the great challenges in modern bioinformatics. In many living beings (including the human), every gene is present in two copies, inherited from the two parents, the so-called haplotypes. In this paper, we propose a simple combinatorial model for classifying the set of haplotypes in a population according to their responsibility for a certain genetic disease. This model is based on the minimum-ones 2SAT problem with uniform clauses. The minimum-ones 2SAT problem asks for a satisfying assignment to a satisfiable formula in 2CNF which sets a minimum number of variables to true. This problem is well-known to be NP-hard, even in the case where all clauses are uniform, i.e., do not contain a positive and a negative literal. We analyze the approximability and present the first non-trivial exact algorithm for the uniform minimum-ones 2SAT problem with a running time of O(1.21061(n)) on a 2SAT formula with n variables. We also show that the problem is fixed-parameter tractable by showing that our algorithm can be adapted to verify in O*(2(k)) time whether an assignment with at most k true variables exists.

关键词： Exact algorithms fixed-parameter algorithms minimum-ones 2SAT haplotypes

来源：评论

学校读者我要写书评

暂无评论

Designing and implementing algorithms for the closest string problem

引用

THEORETICAL COMPUTER SCIENCE 2019年 786卷 32-43页

作者： Yuasa, Shota Chen, Zhi-Zhong Ma, Bin Wang, Lusheng Tokyo Denki Univ Div Informat Syst Design Hatoyama Saitama 3500394 Japan Univ Waterloo Sch Comp Sci 200 Univ Ave W Waterloo ON N2L 3G1 Canada City Univ Hong Kong Dept Comp Sci Kowloon Tat Chee Ave Hong Kong Peoples R China City Univ Hong Kong Shenzhen Res Inst Shenzhen Hitech Ind Pk Shenzhen Peoples R China

Given a set of n strings of length L and a radius d, the closest string problem (CSP for short) asks for a string t(sol) that is within a Hamming distance of d to each of the given strings. It is known that the problem is NP-hard and its optimization version admits a polynomial time approximation scheme (PTAS). A number of parameterized algorithms have been then developed to solve the problem when d is small. Among them, the relatively new ones have not been implemented before and their performance in practice was unknown. In this study, we implement all of them by careful engineering. For those that have been implemented before, our implementation is much faster. For some of those that have not been implemented before, our experimental results show that there exist huge gaps between their theoretical and practical performances. We also design a new parameterized algorithm for the binary case of CSP. The algorithm is deterministic and runs in O (n(2)L + n(2)d. 6.16(d)) time, while the previously best deterministic algorithm runs in O (nL + nd(3). 6.731(d)) time. (C) 2018 Elsevier B.V. All rights reserved.

关键词： The closest string problem fixed-parameter algorithms Computational biology Algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：