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

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

来源：评论

学校读者我要写书评

暂无评论

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 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

来源：评论

学校读者我要写书评

暂无评论

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 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

来源：评论

学校读者我要写书评

暂无评论

Orientable burning number of graphs☆

引用

DISCRETE APPLIED MATHEMATICS 2025年 367卷 116-128页

作者： Courtiel, Julien Dorbec, Paul Gima, Tatsuya Lecoq, Romain Otachi, Yota Normandie Univ UNICAEN ENSICAEN CNRSGREYC F-14000 Caen France Hokkaido Univ Sapporo Japan Nagoya Univ Nagoya Japan

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.

关键词： Burning number Graph orientation fixed-parameter algorithm

来源：评论

学校读者我要写书评

暂无评论

Orientable Burning Number of Graphs 18th

Orientable Burning Number of Graphs

引用

18th International Conference and Workshops on algorithms and Computation (WALCOM)

作者： Courtiel, Julien Dorbec, Paul Gima, Tatsuya Lecoq, Romain Otachi, Yota Normandie Univ UNICAEN ENSICAEN CNRSGREYC F-14000 Caen France Nagoya Univ Nagoya Aichi Japan

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).

关键词： Burning number Graph orientation fixed-parameter algorithm

来源：评论

学校读者我要写书评

暂无评论

fixed-parameter tractability for the Tree Assembly problem

引用

THEORETICAL COMPUTER SCIENCE 2021年 886卷 3-12页

作者： Shi, Feng You, Jie Zhang, Zhen Liu, Jingyi 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 Alibaba Grp Hangzhou 311121 Peoples R China

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.

关键词： Tree Assembly problem fixed-parameter algorithm Tree editing distance Subforest isomorphism

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：