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

6th International Symposium on Bioinformatics Research and Applications

作者： Doan, Duong D. Evans, Patricia A. Univ New Brunswick Fredericton NB Canada

ISBN: (纸本)9783642130779

The problem of computing the minimum number of recombination events for general pedigrees with two sites for all members is investigated. We show that this NP-hard problem can be parametrically reduced to the Bipartization by Edge Removal problem and therefore can be solved by an O(2(k) . n(2)) exact algorithm, where n is the number of members and k is the number of recombination events.

关键词： fixed-parameter algorithm haplotyping pedigree

来源：评论

学校读者我要写书评

暂无评论

A fixed-parameter algorithm for the maximum agreement forest problem on multifurcating trees

引用

Science China(Information Sciences) 2016年第1期59卷 66-79页

作者： Feng SHI Jianxin WANG Yufei YANG Qilong FENG Weilong LI Jianer CHEN School of Information Science and Engineering Central South University Department of Computer Science and Engineering Texas A&M University College Station

The Maximum Agreement Forest(MAF) problem on two given phylogenetic trees is an important NP-hard problem in the field of computational biology. In this paper, we study the parameterized version of the MAF problem: given two unrooted(multifurcating) phylogenetic trees Tand Twith the same leaf-label set L, and a parameter k, either construct an agreement forest of at most k trees for Tand T, or report that no such a forest exists. Whether there is a fixed-parameter tractable algorithm for this problem was posed as an open problem several times in the literature. In this paper, we resolve this open problem by presenting a parameterized algorithm of running time O(4~kn~5) for the problem.

关键词： computational biology multifurcating phylogenetic tree maximum agreement forest TBR distance fixed-parameter algorithm

来源：评论

学校读者我要写书评

暂无评论

Charge and reduce: A fixed-parameter algorithm for String-to-String Correction

引用

DISCRETE OPTIMIZATION 2011年第1期8卷 41-49页

作者： Abu-Khzam, Faisal N. Fernau, Henning Langston, Michael A. Lee-Cultura, Serena Stege, Ulrike Lebanese Amer Univ Dept Comp Sci & Math Beirut Lebanon Univ Trier FB Abt Informat 4 D-54286 Trier Germany Univ Tennessee Dept Elect Engn & Comp Sci Knoxville TN 37996 USA Univ Victoria Dept Comp Sci Victoria BC V8W 2Y2 Canada

String distance problems typically ask for a minimum number of permitted operations to transform one string into another. Such problems find application in a wide variety of areas, including error-correcting codes, parsing theory, speech recognition, and computational biology, to name a few. Here we consider a classic string distance problem, the NP-complete STRING-TO-STRING CORRECTION problem, first studied by Wagner some 35 years ago. In this problem, we are asked whether it is possible to transform string x into string y with at most k operations on x, where permitted operations are single-character deletions and adjacent character exchanges. We prove that STRING-TO-STRING CORRECTION is fixed-parameter tractable, for parameter k, and present a simple fixed-parameter algorithm that solves the problem in O(2(k)n) time. We also devise a bounded search tree algorithm, and introduce a bookkeeping technique that we call charge and reduce. This leads to an algorithm whose running time is O(1.618 1(k)n). (C) 2011 Published by Elsevier B.V.

关键词： fixed-parameter algorithm String-to-String Correction Charge and reduce

来源：评论

学校读者我要写书评

暂无评论

A fixed-parameter algorithm for guarding 1.5D terrains

引用

THEORETICAL COMPUTER SCIENCE 2015年 595卷 130-142页

作者： Khodakarami, Farnoosh Didehvar, Farzad Mohades, Ali Amirkabir Univ Technol Dept Math & Comp Sci Lab Algorithms & Computat Geometry Tehran Iran

A 1.50 terrain is a region on a plane determined by an x-monotone polygonal chain. A set G of points on the terrain is called a guarding set if every point on the terrain is seen by some point in G. In the 1.5D terrain guarding problem we are given a 1.5D terrain and the goal is to find the minimum guarding set for the given input terrain. It is proved that this problem is NP-hard and the only previous theoretical results for this problem involve approximation. In this paper, we turn to fixed-parameter tractability. We present "depth of terrain onion peeling" as a new geometric parameter. Based on this parameter, we give an upper bound for the treewidth of the terrain visibility graph. By presenting a dynamic programming algorithm, we show that the 1.50 terrain guarding problem is fixed-parameter tractable with respect to this parameter. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Guarding 1.5D terrain Onion peeling Tree decomposition fixed-parameter algorithm

来源：评论

学校读者我要写书评

暂无评论

A fixed-parameter algorithm for a unit-execution-time unit-communication-time tasks scheduling problem with a limited number of identical processors

引用

RAIRO-OPERATIONS RESEARCH 2022年第5期56卷 3777-3788页

作者： Kordon, Alix Munier Tang, Ning Sorbonne Univ LIP6 CNRS F-75005 Paris France

This paper considers the minimization of the maximum lateness for a set of dependent tasks with unit duration, unit communication delays release times and due dates. The number of processors is limited, and each task requires one processor for its execution. A time window built from an upper bound of the minimum maximum lateness is associated to each task. The parameter considered is the pathwidth of the associated interval graph. A fixed-parameter algorithm based on a dynamic programming approach is developed to solve this optimization problem. This is, as far as we know, the first fixed-parameter algorithm for a scheduling problem with communication delays and a limited number of processors.

关键词： Scheduling communication delays minimization of the maximum lateness fixed-parameter algorithm

来源：评论

学校读者我要写书评

暂无评论

A fixed-parameter algorithm for the vertex cover P₃ problem

引用

INFORMATION PROCESSING LETTERS 2015年第2期115卷 96-99页

作者： Tu, Jianhua Beijing Univ Chem Technol Sch Sci Beijing 100029 Peoples R China

A subset F of vertices of a graph G is called a vertex cover P-t set if every path of order t in G contains at least one vertex from F. Denote by psi t(G) the minimum cardinality of a vertex cover P-t set in G. The vertex cover P-t (VCPt) problem is to find a minimum vertex cover P-t set. The VCPt problem is NP-hard for any integer t >= 2. In this paper, we restrict our attention to the VCP3 problem and present a fixed-parameter algorithm with runtime O(2(k)k(3.376) + n(4)m) for the VCP3 problem. Here, n denotes the number of vertices, m denotes the number of the edges, k denotes the size of the vertex cover P-3 set searched for. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Combinatorial problem fixed-parameter algorithm Vertex cover P-3 problem Iterative compression

来源：评论

学校读者我要写书评

暂无评论

Improved fixed-parameter algorithm for the Tree Containment Problem on Unrooted Phylogenetic Network

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2022年第6期19卷 3539-3552页

作者： Shi, Feng Li, Hangcheng Rong, Guozhen Zhang, Zhen Wang, Jianxin Cent South Univ Sch Comp Sci & Engn Changsha 410083 Peoples R China Cent South Univ Hunan Prov Key Lab Bioinformat Changsha 410083 Peoples R China

Phylogenetic trees are unable to represent the evolutionary process for a collection of species if reticulation events happened, and a generalized model named phylogenetic network was introduced consequently. However, the representation of the evolutionary process for one gene is actually a phylogenetic tree that is "contained" in the phylogenetic network for the considered species containing the gene. Thus a fundamental computational problem named Tree Containment problem arises, which asks whether a phylogenetic tree is contained in a phylogenetic network. The previous research on the problem mainly focused on its rooted version of which the considered tree and network are rooted, and several algorithms were proposed when the considered network is binary or structurerestricted. There is almost no algorithm for its unrooted version except the recent fixed-parameter algorithm with runtime O(4(k)n(2)) , where k and n are the reticulation number and size of the considered unrooted binary phylogenetic network N, respectively. As the runtime is a little expensive when considering big values of k, we aim to improve it and successfully propose a fixed-parameter algorithm with runtime Oo2:594kn2THORN in the paper. Additionally, we experimentally show its effectiveness on biological data and simulated data.

关键词： Phylogeny Vegetation Runtime Uncertainty Computational modeling Time complexity Sorting Phylogenetic tree phylogenetic network unrooted tree containment problem fixed-parameter algorithm

来源：评论

学校读者我要写书评

暂无评论

A fixed-parameter algorithm for Scheduling Unit Dependent Tasks with Unit Communication Delays 27th

A Fixed-Parameter Algorithm for Scheduling Unit Dependent Ta...

引用

27th International European Conference on Parallel and Distributed Computing (Euro-Par)

作者： Tang, Ning Kordon, Alix Munier Sorbonne Univ LIP6 CNRS F-75005 Paris France

ISBN: (纸本)9783030856656;9783030856649

This paper considers the minimization of the makespan for a set of dependent tasks with unit duration and unit communication delays. Given an upper bound of the makespan, release dates and deadlines of the tasks can be computed. Time windows are defined accordingly. We prove that our scheduling problem is fixed-parameter tractable;the parameter is the maximum number of tasks that are schedulable at the same time considering time windows. A fixed-parameter algorithm based on a dynamic programming approach is developed and proved to solve this optimization problem. This is, as far as we know, the first fixed-parameter algorithm for a scheduling problem with communication delays.

关键词： Scheduling Communication delays Makespan fixed-parameter algorithm

来源：评论

学校读者我要写书评

暂无评论

A fixed parameter algorithm for optimal convex partitions

引用

JOURNAL OF DISCRETE algorithmS 2008年第4期6卷 561-569页

作者： Spillner, Andreas Univ East Anglia Norwich Norfolk England

We present a fixed-parameter algorithm for the Minimum Convex Partition and the Minimum Weight Convex Partition problem. The algorithm is based on techniques developed for the Minimum Weight Triangulation problem. On a set P of n points the algorithm runs in O(2(k)k(4)n(3) + n logn) time. The parameter k is the number of points in P lying in the interior of the convex hull of P. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Convex partition fixed-parameter algorithm

来源：评论

学校读者我要写书评

暂无评论

fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2018年第2期270卷 419-429页

作者： Cambazard, Hadrien Catusse, Nicolas Univ Grenoble Alpes CNRS Grenoble INP G SCOP F-38000 Grenoble France

Given a set P of n points with their pairwise distances, the traveling salesman problem (TSP) asks for a shortest tour that visits each point exactly once. A TSP instance is rectilinear when the points lie in the plane and the distance considered between two points is the 11 distance. In this paper, a fixed parameter algorithm for the Rectilinear TSP is presented and relies on techniques for solving TSP on bounded-treewidth graphs. It proves that the problem can be solved in 0(nh7(h)) where h <= n denotes the number of horizontal lines containing the points of P. The same technique can be directly applied to the problem of finding a shortest rectilinear Steiner tree that interconnects the points of P providing a 0(nh5(h)) time complexity. Both bounds improve over the best time bounds known for these problems. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Traveling salesman Rectilinear traveling salesman problem Rectilinear Steiner tree problem fixed-parameter algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：