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.
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.
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.
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.
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.
In this paper, we introduce the problem of finding an orientation of a given undirected graph that maximizes the burning number of the resulting directed graph. We show that the problem is polynomial-time solvable on ...
详细信息
In this paper, we introduce the problem of finding an orientation of a given undirected graph that maximizes the burning number of the resulting directed graph. We show that the problem is polynomial-time solvable on K & odblac;nig-Egerv & aacute;ry graphs (and thus on bipartite graphs) and that an almost optimal solution can be computed in polynomial time for perfect graphs. On the other hand, we show that the problem is NP-hard in general and W[1]-hard parameterized by the target burning number. The hardness results are complemented by several fixed-parameter tractable results parameterized by structural parameters. Our main result in this direction shows that the problem is fixed-parameter tractable parameterized by cluster vertex deletion number plus clique number (and thus also by vertex cover number). (c) 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
In this paper, we introduce the problem of finding an orientation of a given undirected graph that maximizes the burning number of the resulting directed graph. We show that the problem is polynomial-time solvable on ...
详细信息
ISBN:
(纸本)9789819705658;9789819705665
In this paper, we introduce the problem of finding an orientation of a given undirected graph that maximizes the burning number of the resulting directed graph. We show that the problem is polynomial-time solvable on Konig-Egervary graphs (and thus on bipartite graphs) and that an almost optimal solution can be computed in polynomial time for perfect graphs. On the other hand, we show that the problem is NP-hard in general and W[1]-hard parameterized by the target burning number. The hardness results are complemented by several fixed-parameter tractable results parameterized by structural parameters. Our main result in this direction shows that the problem is fixed-parameter tractable parameterized by cluster vertex deletion number plus clique number (and thus also by vertex cover number).
Calculating the "distance" between two given objects with respect to a designated "editing" operation is a hot research area in bioinformatics, where the "distance" is always defined as t...
详细信息
Calculating the "distance" between two given objects with respect to a designated "editing" operation is a hot research area in bioinformatics, where the "distance" is always defined as the minimum number of the "editing" operations required to transform one object into the other one. One of the famous problems in the area is the Minimum Common String Partition problem, which is the simplified variant of the Minimum Tree Cut/Paste Distance problem. Within the paper, we consider another simplified variant of the Minimum Tree Cut/Paste Distance problem, named Tree Assembly problem, of which the edge-deletion operations are specified. More specifically, the Tree Assembly problem aims to transform a given forest into a given tree by edge-addition operations only. In our investigations, we present a fixed-parameter algorithm with runtime 2(O(klogk)) n(O(1)) for the Tree Assembly problem, where k is the number of trees in the given forest, and n is the number of nodes in the given tree and forest. Additionally, we give a polynomial time algorithm for a restricted variant of the problem. (C) 2021 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.
暂无评论