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

Improved parameterized algorithms for minimum link-length rectilinear spanning path problem

THEORETICAL COMPUTER SCIENCE 2014年第Part2期560卷 158-171页

作者： Feng, Qilong Wang, Jianxin Xu, Chao Yao, Jinyi Chen, Jianer Cent S Univ Sch Informat Sci & Engn Changsha 410083 Hunan Peoples R China Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA

The parameterized Minimum Link-Length Rectilinear Spanning Path problem in the d-dimensional Euclidean space R-d (d-RSP), for a given set S of n points in R-d and a positive integer k, is to find a rectilinear spanning path P with at most k line-segments that cover all points in S, where all line-segments in P are axis-parallel. In this paper, we study a constrained d-RSP problem (Constrained d-RSP problem) in which each line-segment l in the spanning path must cover all the points in S that share the same line with l. By applying the branch-and-search and dynamic programming techniques, a parameterized algorithm with running time 0*((1 + root 1 + 4(d - 1)(2))(k)) is given for the Constrained d-RSP problem, which significantly improves the current best result 0*((0.74dk)(k)). (C) 2014 Elsevier B.V. All rights reserved.

关键词： Rectilinear spanning path parameterized algorithm Line cover Axis-parallel line

来源：评论

学校读者我要写书评

暂无评论

On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering

引用

THEORETICAL COMPUTER SCIENCE 2021年 873卷 16-24页

作者： Liu, Yunlong Chen, Jie Huang, Jingui Wang, Jianxin Hunan Normal Univ Coll Informat Sci & Engn Hunan Prov Key Lab Intelligent Comp & Language In Changsha Peoples R China Hunan Xiangjiang Artificial Intelligence Acad Changsha Peoples R China Cent South Univ Sch Comp Sci & Engn Changsha Peoples R China

Given a graph G = (V, E) with a vertex ordering is a k-page book embedding of G. This problem is NP-complete even for any fixed k greater than 3. Recently, Bhore et al. (2019, 2020) [1,2] presented a parameterized al... 详细信息

Given a graph G = (V, E) with a vertex ordering <=, the FIXED-ORDER BOOK THICKNESS problem asks whether there is a page assignment sigma such that <<=, sigma > is a k-page book embedding of G. This problem is NP-complete even for any fixed k greater than 3. Recently, Bhore et al. (2019, 2020) [1,2] presented a parameterized algorithm with respect to the pathwidth kappa of the vertex ordering. In this paper, we first re-analyze the running time for Bhore et al.'s algorithm, and prove a bound of 2(O(kappa 2)).vertical bar V vertical bar improving Bhore et al.'s bound of kappa(O(kappa 2)).vertical bar V vertical bar. Then, we show that FIXED-ORDER BOOK THICKNESS parameterized by the pathwidth of the vertex ordering does not admit a polynomial kernel unless NP subset of coNP/poly. Finally, we show that a generalized FIXED-ORDER BOOK THICKNESS problem, in which a budget of at most c crossings over all pages was given, admits a parameterized algorithm running in time (c + 2)(O(kappa 2)).vertical bar V vertical bar. (C) 2021 Published by Elsevier B.V.

关键词： parameterized algorithm Fixed-order book thickness Pathwidth of the vertex ordering Kernel lower bound

来源：评论

学校读者我要写书评

暂无评论

Simple and Improved parameterized algorithms for Multiterminal Cuts

引用

THEORY OF COMPUTING SYSTEMS 2010年第4期46卷 723-736页

作者： Xiao, Mingyu Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 610054 Peoples R China

Given a graph G = (V, E) with n vertices and m edges, and a subset T of k vertices called terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of at most l edges (non-terminal vertices), whose removal from G separates each terminal from all the others. These two problems are NP-hard for k = 3 but well-known to be polynomial-time solvable for k = 2 by the flow technique. In this paper, based on a notion farthest minimum isolating cut, we design several simple and improved algorithms for Multiterminal Cut. We show that Edge Multiterminal Cut can be solved in O(2(l)kT (n, m)) time and Vertex Multiterminal Cut can be solved in O(k(l)T (n, m)) time, where T (n, m) = O(min(n(2/3), m(1/2)) m) is the running time of finding a minimum (s, t) cut in an unweighted graph. Furthermore, the running time bounds of our algorithms can be further reduced for small values of k: Edge 3-Terminal Cut can be solved in O(1.415(l)T (n, m)) time, and Vertex {3, 4, 5, 6}-Terminal Cuts can be solved in O(2.059(l)T (n, m)), O(2.772(l)T (n, m)), O(3.349(l)T (n, m)) and O(3.857(l)T (n, m)) time respectively. Our results on Multiterminal Cut can also be used to obtain faster algorithms for Multicut: O((min(root 2k, l) + 1)(2k)2(l)T (n, m))-time algorithm for Edge Multicut and O((2k)Tk+l/2 (n, m))-time algorithm for Vertex Multicut.

关键词： Graph algorithm parameterized algorithm Multiterminal cut Multicut

来源：评论

学校读者我要写书评

暂无评论

Improved parameterized algorithms for Network Query Problems

引用

algorithmICA 2019年第6期81卷 2270-2316页

作者： Pinter, Ron Y. Shachnai, Hadas Zehavi, Meirav Technion Dept Comp Sci IL-3200003 Haifa Israel

In the Partial Information Network Query (PINQ) problem, we are given a host graph H, and a pattern P whose topology is partially known. We seek a connected subgraph of H that resemblesP. PINQ is a generalization of Subgraph Isomorphism, where the topology of P is known, and Graph Motif, where the topology of P is unknown. This generalization addresses the major challenge of analyzing biological networks in the absence of certain topological data. In this paper, we use a non-standard hybridization of algebraic and combinatorial tools to develop an exact parameterized algorithm as well as an FPT-approximation scheme for PINQ.

关键词： parameterized algorithm Narrow sieves Partial information network query Alignment network query Graph motif

来源：评论

学校读者我要写书评

暂无评论

Deterministic parameterized algorithms for the Graph Motif problem

引用

DISCRETE APPLIED MATHEMATICS 2016年第0期213卷 162-178页

作者： Pinter, Ron Y. Shachnai, Hadas Zehavi, Meirav Technion Israel Inst Technol Dept Comp Sci IL-3200003 Haifa Israel

We study the classic GRAPH MOTIF problem. Given a graph G = (V, E) with a set of colors for each node, and a multiset M of colors, we seek a subtree T subset of G, and a coloring assigning to each node in T a color from its set, such that T carries exactly (also with respect to multiplicity) the colors in M. GRAPH MOTIF plays a central role in the study of pattern matching problems, primarily motivated from the analysis of complex biological networks. Previous algorithms for GRAPH MOTIF and its variants either rely on techniques for developing randomized algorithms that - if derandomized - render them inefficient, or the algebraic narrow sieves technique for which there is no known derandomization. In this paper, we present fast deterministic parameterized algorithms for GRAPH MOTIF and its variants. Specifically, we give such-an algorithm for the more general GRAPH MOTIF WITH DELETIONS problem, followed by faster algorithms for GRAPH MOTIF and other well-studied special cases. Our algorithms make non-trivial use of representative families, and a novel tool that we call guiding trees, together enabling the efficient construction of the output tree. (C) 2016 Elsevier B.V. All rights reserved.

关键词： parameterized algorithm Graph motif Representative family Guiding tree

来源：评论

学校读者我要写书评

暂无评论

Efficient parameterized algorithms for biopolymer structure-sequence alignment

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2006年第4期3卷 423-432页

作者： Song, Yinglei Liu, Chunmei Huang, Xiuzhen Malmberg, Russell L. Xu, Ying Cai, Liming Univ Georgia Dept Comp Sci Athens GA 30602 USA Arkansas State Univ Dept Comp Sci State Univ AR 72467 USA Univ Georgia Dept Plant Biol Athens GA 30602 USA Univ Georgia Dept Biochem & Mol Biol Athens GA 30602 USA

Computational alignment of a biopolymer sequence (e. g., an RNA or a protein) to a structure is an effective approach to predict and search for the structure of new sequences. To identify the structure of remote homologs, the structure-sequence alignment has to consider not only sequence similarity, but also spatially conserved conformations caused by residue interactions and, consequently, is computationally intractable. It is difficult to cope with the inefficiency without compromising alignment accuracy, especially for structure search in genomes or large databases. This paper introduces a novel method and a parameterized algorithm for structure-sequence alignment. Both the structure and the sequence are represented as graphs, where, in general, the graph for a biopolymer structure has a naturally small tree width. The algorithm constructs an optimal alignment by finding in the sequence graph the maximum valued subgraph isomorphic to the structure graph. It has the computational time complexity O(k(t)N(2)) for the structure of N residues and its tree decomposition of width t. Parameter k, small in nature, is determined by a statistical cutoff for the correspondence between the structure and the sequence. This paper demonstrates a successful application of the algorithm to RNA structure search used for noncoding RNA identification. An application to protein threading is also discussed.

关键词： structure-sequence alignment tree decomposition parameterized algorithm dynamic programming RNA structure homology search protein threading

来源：评论

学校读者我要写书评

暂无评论

Research on parameterized algorithms of the individual haplotyping problem

引用

Journal of Bioinformatics and Computational Biology 2007年第3期5卷 795-816页

作者： Xie, Minzhu Chen, Jian'er Wang, Jianxin School of Information Science and Engineering Central South University Changsha Hunan Province 410083 China College of Physics and Information Science Hunan Normal University Changsha Hunan Province 410083 China

The individual haplotyping problem is a computing problem of reconstructing two haplotypes for an individual based on several optimal criteria from one's fragments sequencing data. This paper is based on the fact that the length of a fragment and the number of the fragments covering a SNP (single nucleotide polymorphism) site are both very small compared with the length of a sequenced region and the total number of the fragments and introduces the parameterized haplotyping problems. With m fragments whose maximum length is k₁, n SNP sites and the number of the fragments covering a SNP site no more than k₂, our algorithms can solve the gapless MSR (Minimum SNP Removal) and MFR (Minimum Fragment Removal) problems in the time complexity O(nk₁k₂ + m log m + nk₂ + mk₁) and O(mk₂² + mk₁ k₂ + m log m + nk₂ + mk₁) respectively. Since, the value of k₁ and k₂ are both small (about 10) in practice, our algorithms are more efficient and applicable compared with the algorithms of V. Bafna et al. of time complexity O(mn²) and O(m²n + m³), respectively. © Imperial College Press.

关键词： Genotype Haplotype parameterized algorithm SNPs (single nucleotide polymorphisms)

来源：评论

学校读者我要写书评

暂无评论

Exact and parameterized algorithms for Edge Dominating Set in 3-Degree Graphs

Exact and Parameterized Algorithms for Edge Dominating Set i...

引用

4th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Xiao, Mingyu Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 610054 Peoples R China

ISBN: (纸本)9783642174605

Given a graph G = (V, E), the edge dominating set problem is to find a minimum set M subset of E such that each edge in E - M has at least one common endpoint with an edge in M. The edge dominating set problem is an important graph problem and has been extensively studied. It is well known that the problem is NP-hard, even when the graph is restricted to a planar or bipartite graph with maximum degree 3. In this paper, we show that the edge dominating set problem in graphs with maximum degree 3 can be solved in O*(1.2721(n)) time and polynomial space, where n is the number of vertices in the graph. We also show that there is an O*(2.2306(k))-time polynomial-space algorithm to decide whether a graph with maximum degree 3 has an edge dominating set of size k or not. Above two results improve previously known results on exact and parameterized algorithms for this problem.

关键词： Edge Dominating Set Exact algorithm parameterized algorithm Cubic Graph

来源：评论

学校读者我要写书评

暂无评论

Approximation and parameterized algorithms for Balanced Connected Partition Problems 8th

Approximation and Parameterized Algorithms for Balanced Conn...

引用

8th International Conference on algorithms and Discrete Applied Mathematics

作者： Moura, Phablo F. S. Ota, Matheus Jun Wakabayashi, Yoshiko Univ Fed Minas Gerais Dept Ciencia Computacao Belo Horizonte MG Brazil Univ Waterloo Dept Combinator & Optimizat Waterloo ON Canada Univ Sao Paulo Inst Matemat & Estat Sao Paulo Brazil

ISBN: (纸本)9783030950170;9783030950187

For a given integer k >= 2, partitioning a connected graph into k vertex-disjoint connected subgraphs of similar (or fixed) orders is a classical problem that has been intensively investigated since late seventies. A connected k-partition of a graph is a partition of its vertex set into classes such that each one induces a connected subgraph. Given a connected graph G = (V, E) and a weight function w : V -> Q >=, the balanced connected k-partition problem looks for a connected k-partition of G into classes of roughly the same weight. To model this concept of balance, we seek connected k-partitions that either maximize the weight of a lightest class (MAX-MIN BCPk) or minimize the weight of a heaviest class (MIN-MAX BCPk). These problems, known to be NP-hard, are equivalent only when k/2. We present a simple pseudo-polynomial k/2-approximation algorithm for MIN-MAX BCPk that runs in time O(W vertical bar V vertical bar vertical bar E vertical bar), where W = Sigma(v is an element of V) w(v);then, using a scaling technique, we obtain a (polynomial) (k/2 + epsilon)-approximation with running-time O(vertical bar V vertical bar(3)vertical bar E vertical bar/epsilon), for any fixed epsilon > 0. Additionally, we propose a fixed-parameter tractable algorithm for the unweighted MAX-MIN BCP (where k is part of the input) parameterized by the size of a vertex cover.

关键词： Balanced connected partition Approximation algorithm parameterized algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient parameterized algorithms for biopolymer structure-sequence alignment

Efficient parameterized algorithms for biopolymer structure-...

引用

5th International Workshop on algorithms in Bioinformatics (WABI 2005)

关键词： structure-sequence alignment tree decomposition parameterized algorithm dynamic programming RNA structure homology search protein threading

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：