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

fixed-parameter algorithms FOR FINDING AGREEMENT SUPERTREES

SIAM JOURNAL ON COMPUTING 2015年第2期44卷 384-410页

作者： Fernandez-Baca, David Guillemot, Sylvain Shutters, Brad Vakati, Sudheer Iowa State Univ Dept Comp Sci Ames IA 50011 USA Hungarian Acad Sci Comp & Automat Res Inst H-1111 Budapest Hungary Univ Wisconsin Dept Comp Sci La Crosse WI 54601 USA Amazon Com Seattle WA 98108 USA

We study the agreement supertree approach for combining rooted phylogenetic trees when the input trees do not fully agree on the relative positions of the taxa. We consider two ways to deal with such conflict. The first is to contract a set of edges in the input trees so that the resulting trees have an agreement supertree. We show that this problem is NP-complete and give a fixed-parameter tractable (FPT) algorithm for the problem parameterized by the number of input trees and the number of edges contracted. The second approach is to remove a set of taxa from the input trees so that the resulting trees have an agreement supertree. Guillemot and Berry (2010) gave an FPT algorithm for this problem when the input trees are all binary. We give an FPT algorithm for the more general case where the input trees are allowed to have arbitrary degree.

关键词： phylogenies fixed-parameter algorithms computational biology agreement

来源：评论

学校读者我要写书评

暂无评论

fixed-parameter algorithms for scaffold filling

引用

THEORETICAL COMPUTER SCIENCE 2015年第C期568卷 72-83页

作者： Bulteau, Laurent Carrieri, Anna Paola Dondi, Riccardo Tech Univ Berlin Dept Software Engn & Theoret Comp Sci Berlin Germany Univ Milano Bicocca Dipartimento Informat Sistemist & Comunicaz Milan Italy Univ Bergamo Dipartimento Sci Umane & Soc Bergamo Italy

The new sequencing technologies, called next-generation sequencing, provide a huge amount of data that can be used to reconstruct genomes. However, the methods applied to reconstruct genomes often are not able to reconstruct a complete genome and provide only an incomplete information. Here we consider two combinatorial problems that aim to reconstruct complete genomes by inserting a collection of missing genes. The first problem we consider, called One-sided scaffold filling, given an incomplete genome B and a complete genome A, asks for the insertion of missing genes into an incomplete genome B with the goal of maximizing the common adjacencies between genomes B' (resulting from the insertion of missing genes in B) and A. The second problem, called Two-sided scaffold filling, given two incomplete genomes A, B, asks for the insertion of missing genes into both genomes so that the resulting genomes A' and B' have the same multiset of genes and the number of common adjacencies between A' and B' is maximized. Both problems were proved to be NP-hard, while their parameterized complexity, when the parameter is the number of common adjacencies of the resulting genomes, was left as an open problem. In this paper, we settle this open problem by presenting fixed-parameter algorithms for One-sided scaffold filling and Two-sided scaffold filling. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Scaffold filling Genome comparison Computational biology fixed-parameter algorithms

来源：评论

学校读者我要写书评

暂无评论

fixed-parameter algorithms for (k, r)-Center in Planar Graphs and Map Graphs

引用

ACM TRANSACTIONS ON algorithms 2005年第1期1卷 33-47页

作者： Demaine, Erik D. Fomin, Fedor V. Hajiaghayi, Mohammadtaghi Thilikos, Dimitrios M. MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA Univ Bergen Dept Informat N-5020 Bergen Norway Natl & Capodistrian Univ Athens Dept Math GR-15784 Athens Greece

The (k, r) -center problem asks whether an input graph G has <= k vertices (called centers) such that every vertex of G is within distance <= r from some center. In this article, we prove that the (k, r)-center problem, parameterized by k and r, is fixed-parameter tractable (FPT) on planar graphs, i.e., it admits an algorithm of complexity f (k, On") where the function f is independent of n. In particular, we show that f (k, r) = 20(r log) where the exponent of the exponential term grows sublinearly in the number of centers. Moreover, we prove that the same type of FPT algorithms can be designed for the more general class of map graphs introduced by Chen, Grigni, and Papadimitriou. Our results combine dynamic-programming algorithms for graphs of small branchwidth and a graph theoretic result bounding this parameter in terms of k and r. Finally, a byproduct of our algorithm is the existence of a PTAS for the r -domination problem in both planar graphs and map graphs. Our approach builds on the seminal results of Robertson and Seymour on Graph Minors, and as a result is much more powerful than the previous machinery of Alber et al. for exponential speedup on planar graphs. To demonstrate the versatility of our results, we show how our algorithms can be extended to general parameters that are "large" on grids. In addition, our use of branchwidth instead of the usual treewidth allows us to obtain much faster algorithms, and requires more complicated dynamic programming than the standard leaf/introduce/forget/join structure of nice tree decompositions. Our results are also unique in that they apply to classes of graphs that are not minor-closed, namely, constant powers of planar graphs and map graphs.

关键词： (k, r)-center fixed-parameter algorithms domination planar graph map graph

来源：评论

学校读者我要写书评

暂无评论

Randomized fixed-parameter algorithms for the Closest String Problem

引用

ALGORITHMICA 2016年第1期74卷 466-484页

作者： Chen, Zhi-Zhong Ma, Bin Wang, Lusheng Tokyo Denki Univ Div Informat Syst Design Hiki Saitama 3500394 Japan Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China

Given a set of strings of equal length and an integer , the closest string problem (CSP) requires the computation of a string of length such that for each , where is the Hamming distance between and . The problem is NP-hard and has been extensively studied in the context of approximation algorithms and fixed-parameter algorithms. fixed-parameter algorithms provide the most practical solutions to its real-life applications in bioinformatics. In this paper we develop the first randomized fixed-parameter algorithms for CSP. Not only are the randomized algorithms much simpler than their deterministic counterparts, their time complexities are also significantly better than the previously best known (deterministic) algorithms.

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

来源：评论

学校读者我要写书评

暂无评论

Bounds and fixed-parameter algorithms for Weighted Improper Coloring

引用

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE 2016年 322卷 181-195页

作者： Gudmundsson, Bjarki Agust Magnusson, Tomas Ken Saemundsson, Bjorn Orri Reykjavik Univ Sch Comp Sci ICE TCS Reykjavik Iceland

We study the weighted improper coloring problem, a generalization of defective coloring. We present some hardness results and in particular we show that weighted improper coloring is not fixed-parameter tractable when parameterized by pathwidth. We generalize bounds for defective coloring to weighted improper coloring and give a bound for weighted improper coloring in terms of the sum of edge weights. Finally we give fixed-parameter algorithms for weighted improper coloring both when parameterized by treewidth and maximum degree and when parameterized by treewidth and precision of edge weights. In particular, we obtain a linear-time algorithm for weighted improper coloring of interval graphs of bounded degree.

关键词： graph coloring improper coloring defective coloring weighted improper coloring coloring bounds fixed-parameter algorithms

来源：评论

学校读者我要写书评

暂无评论

fixed-parameter algorithms in Phylogenetics

Fixed-Parameter Algorithms in Phylogenetics

引用

作者： Jens Gramm Arfst Nickelsen Till Tantau

This chapter surveys the use of fixed-parameter algorithms in phylogenetics. A central computational problem in this field is the construction of a likely phylogeny (genealogical tree) for a set of species based on observed differences in the phenotype, differences in the genotype, or given partial phylogenies. Ideally, one would like to construct so-called perfect phylogenies, which arise from an elementary evolutionary model, but in practice one must often be content with phylogenies whose “distance from perfection” is as small as possible. The computation of phylogenies also has applications in seemingly unrelated areas such as genomic sequencing and finding and understanding genes. The numerous computational problems arising in phylogenetics are often NP-complete, but for many natural parametrizations they can be solved using fixed-parameter algorithms. less

关键词： Phylogenetics perfect phylogeny fixed-parameter algorithms fixed-parameter tractable

来源：评论

学校读者我要写书评

暂无评论

Ubiquitous parameterization - Invitation to fixed-parameter algorithms

引用

29th International Symposium on Mathematical Foundations of Computer Science

作者： Niedermeier, R Univ Tubingen Wilhelm Schickard Inst Informat D-72076 Tubingen Germany

ISBN: (纸本)3540228233

Problem parameters are ubiquitous. In every area of computer science, we find all kinds of "special aspects" to the problems encountered. Hence, the study of parameterized complexity for computationally hard problems is proving highly fruitful. The purpose of this article is to stir the reader's interest in this field by providing a gentle introduction to the rewarding field of fixed-paxameter algorithms.

关键词： NP-hardness parameterized complexity fixed-parameter algorithms parameterization

来源：评论

学校读者我要写书评

暂无评论

SPLIT VERTEX DELETION meets VERTEX COVER: New fixed-parameter and exact exponential-time algorithms

引用

INFORMATION PROCESSING LETTERS 2013年第5-6期113卷 179-182页

作者： Cygan, Marek Pilipczuk, Marcin Univ Lugano IDSIA Lugano Switzerland Univ Warsaw Inst Informat PL-00325 Warsaw Poland

In the SPLIT VERTEX DELETION problem, given a graph G and an integer k, we ask whether one can delete k vertices from the graph G to obtain a split graph (i.e., a graph, whose vertex set can be partitioned into two sets: one inducing a clique and the second one inducing an independent set). In this paper we study exact (exponential-time) and fixed-parameter algorithms for SPLIT VERTEX DELETION. We show that, up to a factor quasipolynomial in k and polynomial in n, the SPLIT VERTEX DELETION problem can be solved in the same time as the well-studied VERTEX COVER problem. By plugging in the currently best fixed-parameter algorithm for VERTEX COVER due to Chen et al. [Theor. Comput Sci. 411 (40-42) (2010) 3736-3756], we obtain an algorithm that solves SPLIT VERTEX DELETION in time O(-1.2738(k)k(O(logk)) + n(3)). We show that all maximal induced split subgraphs of a given n-vertex graph can be listed in O(3(n/3) n(O(logn))) time. To achieve our goals, we prove the following structural result that may be of independent interest: for any graph G we may compute a family P of size n(O(logn)) containing partitions of V(C) into two parts, such that for any two disjoint sets X-C, X-I subset of V (G) where G[X-C] is a clique and G[X-I] is an independent set, there is a partition in P which contains all vertices of X-C on one side and all vertices of X-I on the other. Moreover, the family P can be enumerated in O(n(O(logn))) time. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Graph algorithms fixed-parameter algorithms Split graphs Split vertex deletion Branching algorithm

来源：评论

学校读者我要写书评

暂无评论

Finding a minimum spanning tree with a small non-terminal set

引用

THEORETICAL COMPUTER SCIENCE 2025年 1033卷

作者： Hanaka, Tesshu Kobayashi, Yasuaki Kyushu Univ Fukuoka Japan Hokkaido Univ Sapporo Japan

In this paper, we study the problem of finding a minimum weight spanning tree that contains each vertex in a given subset VNT of vertices as an internal vertex. This problem, called MINIMUM WEIGHT NON-TERMINAL SPANNING TREE, includes s-t HAMILTONIAN PATH as a special case, and hence it is NP-hard. In this paper, we first observe that NON-TERMINAL SPANNING TREE, the unweighted counterpart of MINIMUM WEIGHT NON-TERMINAL SPANNING TREE, is already NP-hard on some special graph classes. Moreover, it is W[1]-hard when parameterized by clique- width. In contrast, we give a 3k-vertex kernel and O*(2k)-time algorithm, where k is the size of non-terminal set VNT. The latter algorithm can be extended to MINIMUM WEIGHT NON- TERMINAL SPANNING TREE with the restriction that each edge has a polynomially bounded integral weight. We also show that MINIMUM WEIGHT NON-TERMINAL SPANNING TREE is fixed- parameter tractable parameterized by the number of edges in the subgraph induced by the non-terminal set VNT, extending the fixed-parameter tractability of MINIMUM WEIGHT NON- TERMINAL SPANNING TREE to a more general case. Finally, we give several results for structural parameterization.

关键词： Spanning tree fixed-parameter algorithms parameterized complexity Kernelization

来源：评论

学校读者我要写书评

暂无评论

A Practical fixed-parameter Algorithm for Constructing Tree-Child Networks from Multiple Binary Trees

引用

ALGORITHMICA 2022年第4期84卷 917-960页

作者： van Iersel, Leo Janssen, Remie Jones, Mark Murakami, Yukihiro Zeh, Norbert Delft Univ Technol Delft Inst Appl Math Broekmanweg 6 NL-2628 XE Delft Netherlands Dalhousie Univ Fac Comp Sci 6050 Ave Halifax NS B3H 1W5 Canada

We present the first fixed-parameter algorithm for constructing a tree-child phylo-genetic network that displays an arbitrary number of binary input trees and has the minimum number of reticulations among all such networks. The algorithm uses the recently introduced framework of cherry picking sequences and runs in O ((8k)(k)poly(n, t)) time, where n is the number of leaves of every tree, t is the number of trees, and k is the reticulation number of the constructed network. Moreover, we provide an efficient parallel implementation of the algorithm and show that it can deal with up to 100 input trees on a standard desktop computer, thereby providing a major improvement over previous phylogenetic network construction methods.

关键词： fixed-parameter algorithms Phylogenetic networks Hybridization number

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：