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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Shortest odd paths in undirected graphs with conservative weight functions

引用

DISCRETE APPLIED MATHEMATICS 2024年 357卷 34-50页

作者： Juettner, Alpar Kiraly, Csaba Mendoza-Cadena, Lydia Mirabel Pap, Gyula Schlotter, Ildiko Yamaguchi, Yutaro Eotv Lorand Res Network ELKH ELKH ELTE Egervary Res Grp Budapest Hungary Eotvos Lorand Univ Dept Operat Res Budapest Hungary MTA ELTE Matroid Optimizat Res Grp Budapest Hungary HUN REN Ctr Econ & Reg Stud Budapest Hungary Budapest Univ Technol & Econ Budapest Hungary Osaka Univ Grad Sch Informat Sci & Technol Dept Informat & Phys Sci Osaka Japan

We consider the SHORTEST ODD PATH problem, where given an undirected graph G, a weight function on its edges, and two vertices s and t in G, the aim is to find an (s, t)-path with odd length and, among all such paths, of minimum weight. For the case when the weight function is conservative, i.e., when every cycle has non-negative total weight, the complexity of the SHORTEST ODD PATH problem had been open for 20 years, and was recently shown to be NP-hard. We give a polynomial-time algorithm for the special case when the weight function is conservative and the set E- of negative-weight edges forms a single tree. Our algorithm exploits the strong connection between SHORTEST ODD PATH and the problem of finding two internally vertex-disjoint paths between two terminals in an undirected edgeweighted graph. It also relies on solving an intermediary problem variant called SHORTEST PARITY-CONSTRAINED ODD PATH where for certain edges we have parity constraints on their position along the path. Also, we exhibit two FPT algorithms for solving SHORTEST ODD PATH. The first FPT algorithm is parameterized by |E-|, the number of negative edges, or more generally, by the maximum size of a matching in the subgraph of G spanned by E-, when the weight function is conservative. Our second FPT algorithm is parameterized by the treewidth of G, and the algorithm does not rely on conservativeness. (c) 2024 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC license (http://***/licenses/by- nc/4.0/).

关键词： Shortest odd path Parity constrained odd path fixed-parameter algorithms Treewidth Monadic second-order logic

来源：评论

学校读者我要写书评

暂无评论

High-multiplicity N-fold IP via configuration LP

引用

MATHEMATICAL PROGRAMMING 2023年第1期200卷 199-227页

作者： Knop, Dusan Koutecky, Martin Levin, Asaf Mnich, Matthias Onn, Shmuel Czech Tech Univ Fac Informat Technol Dept Theoret Comp Sci Prague Czech Republic Charles Univ Prague Fac Math & Phys Comp Sci Inst Prague Czech Republic Technion Israel Inst Technol Haifa Israel Hamburg Univ Technol Inst Algorithms & Complex Hamburg Germany

N-fold integer programs (IPs) form an important class of block-structured IPs for which increasingly fast algorithms have recently been developed and successfully applied. We study high-multiplicityN-fold IPs, which encode IPs succinctly by presenting a description of each block type and a vector of block multiplicities. Our goal is to design algorithms which solve N-fold IPs in time polynomial in the size of the succinct encoding, which may be significantly smaller than the size of the explicit (non-succinct) instance. We present the first fixed-parameter algorithm for high-multiplicity N-fold IPs, which even works for convex objectives. Our key contribution is a novel proximity theorem which relates fractional and integer optima of the Configuration LP, a fundamental notion by Gilmore and Gomory [Oper. Res., 1961] which we generalize. Our algorithm for N-fold IP is faster than previous algorithms whenever the number of blocks is much larger than the number of block types, such as in N-fold IP models for various scheduling problems.

关键词： Integer programming Configuration IP fixed-parameter algorithms Scheduling

来源：评论

学校读者我要写书评

暂无评论

parameterized algorithms for generalizations of Directed Feedback Vertex Set

引用

DISCRETE OPTIMIZATION 2022年第0期46卷

作者： Goke, Alexander Marx, Daniel Mnich, Matthias Hamburg Univ Technol Inst Algorithms & Complex Hamburg Germany CISPA Helmholtz Ctr Informat Secur Saarbrucken Germany

The DIRECTED FEEDBACK VERTEX SET (DFVS) problem takes as input a directed graph G and seeks a smallest vertex set S that hits all cycles in G. This is one of Karp's 21 NP-complete problems. Resolving the parameterized complexity status of DFVS was a long-standing open problem until Chen et al. (2008) showed its fixed-parameter tractability via a 4kk!nO(1)-time algorithm, where k = |S|. Here we show fixed-parameter tractability of two generalizations of DFVS:center dot Find a smallest vertex set S such that every strong component of G - S has size at most s: we give an algorithm solving this problem in time 4k(ks + k + s)! middot nO(1). This generalizes an algorithm by Xiao (2017) for the undirected version of the *** dot Find a smallest vertex set S such that every non-trivial strong component of G - S is 1-out-regular: we give an algorithm solving this problem in time 2O(k3) middot nO(1). We also solve the corresponding arc versions of these problems by fixed-parameter algorithms. (c) 2022 Published by Elsevier B.V.

关键词： fixed-parameter algorithms Directed Feedback Vertex Set

来源：评论

学校读者我要写书评

暂无评论

Identifying duplications and lateral gene transfers simultaneously and rapidly

引用

JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY 2022年第1期20卷 2150033-2150033页

作者： Chen, Zhi-Zhong Deng, Fei Wang, Lusheng Tokyo Denki Univ Div Informat Syst Design Hatoyama Saitama 3500394 Japan City Univ Hong Kong Dept Comp Sci Kowloon Tat Chee Ave Hong Kong Peoples R China

This paper deals with the problem of enumerating all minimum-cost LCA-reconciliations involving gene duplications and lateral gene transfers (LGTs) for a given species tree S and a given gene tree G. Previously, [Tofigh A, Hallett M, Lagergren J, Simultaneous identification of duplications and lateral gene transfers, IEEE/ACM Trans Comput Biol Bioinf 517-535, 2011.] gave a fixed-parameter algorithm for this problem that runs in O(m + 3(k)n) time, where m is the number of vertices in S, n is the number of vertices in G, and k is the minimum cost of an LCA-reconciliation between S and G. In this paper, by refining their algorithm, we obtain a new one for the same problem that finds and outputs the solutions in a compact form within O(mn(2) + 3(k)) time. In the most interesting case where 3(k) >= mn(2) , our algorithm is O(n) times faster.

关键词： Phylogenetic trees reconciliations fixed-parameter algorithms enumerate algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：