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 Bipartiz...
详细信息
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.
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: gi...
详细信息
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.
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, pa...
详细信息
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.
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 terrai...
详细信息
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.
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 ...
详细信息
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.
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 ve...
详细信息
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.
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,...
详细信息
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.
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 b...
详细信息
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.
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 ...
详细信息
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.
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 plan...
详细信息
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 fixedparameteralgorithm 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.
暂无评论