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

algorithms for topology-free and alignment network queries

JOURNAL OF DISCRETE algorithmS 2014年 27卷 29-53页

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

In this article we address two pattern matching problems which have important applications to bioinformatics. First we address the topology-free network query problem: Given a set of labels L, a multiset P of labels from L, a graph H = (V-H, E-H) and a function LabelH : V-H (->) 2(L), we need to find a subtree S of H which is an occurrence of P. We provide a parameterized algorithm with parameter k = vertical bar P vertical bar that runs in time O*(2(k)) and whose space complexity is polynomial. We also consider three variants of this problem. Then we address the alignment network query problem: Given two labeled graphs P and H, we need to find a subgraph S of H whose alignment with P is the best among all such subgraphs. We present two algorithms for cases in which P and H belong to certain families of DAGs. Their running times are polynomial and they are less restrictive than algorithms that are available today for alignment network queries. Topology-free and alignment network queries provide means to study the function and evolution of biological networks, and today, with the increasing amount of knowledge regarding biological networks, they are extremely relevant. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Topology-free network query Alignment network query Computational biology parameterized algorithm Subgraph homeomorphism

来源：评论

学校读者我要写书评

暂无评论

Planar graph vertex partition for linear problem kernels

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2013年第5期79卷 609-621页

作者： Wang, Jianxin Yang, Yongjie Guo, Jiong Chen, Jianer Cent S Univ Sch Informat Sci & Engn Changsha 410083 Hunan Peoples R China Univ Saarland D-66123 Saarbrucken Germany Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA

A simple partition of the vertex set of a graph is introduced to analyze kernels for planar graph problems in which vertices and edges not in a solution have small distance to the solution. This method directly leads to improved kernel sizes for several problems, without needing new reduction rules. Moreover, new kernelization algorithms are developed for CONNECTED VERTEX COVER, EDGE DOMINATING SET, and MAXIMUM TRIANGLE PACKING problems, further improving the kernel sizes for these problems. (C) 2012 Elsevier Inc. All rights reserved.

关键词： parameterized algorithm Kernelization Connected vertex cover Edge dominating set Maximum triangle packing

来源：评论

学校读者我要写书评

暂无评论

Orthogonal graph drawing with inflexible edges

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2016年 55卷 26-40页

作者： Blaesius, Thomas Lehmann, Sebastian Rutter, Ignaz KIT Karlsruhe Germany Hasso Plattner Inst Potsdam Germany

We consider the problem of creating plane orthogonal drawings of 4-planar graphs (planar graphs with maximum degree 4) with constraints on the number of bends per edge. More precisely, we have a flexibility function assigning to each edge e a natural number flex(e), its flexibility. The problem FLEXDRAW asks whether there exists an orthogonal drawing such that each edge e has at most flex(e) bends. It is known that FLEXDRAW is NP-hard if flex(e) = 0 for every edge e [1]. On the other hand, FLEXDRAW can be solved efficiently if flex(e) >= 1 [2] and is trivial if flex(e) >= 2 [3] for every edge e. To close the gap between the NP-hardness for flex(e) = 0 and the efficient algorithm for flex(e) >= 1, we investigate the computational complexity of FLEXDRAW in case only few edges are inflexible (i.e., have flexibility 0). We show that for any epsilon > 0 FLEXDRAW is NP-complete for instances with O (n(epsilon)) inflexible edges with pairwise distance Omega(n(1-epsilon)) (including the case where they induce a matching), where n denotes the number of vertices in the graph. On the other hand, we give an EFT-algorithm with running time O (2(k) . n . T-flow(n)), where T-flow(n) is the time necessary to compute a maximum flow in a planar flow network with multiple sources and sinks, and k is the number of inflexible edges having at least one endpoint of degree 4. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Orthgonal graph drawing Bend minimization Planar embedding parameterized algorithm Computational complexity

来源：评论

学校读者我要写书评

暂无评论

A Practical Exact algorithm for the Individual Haplotyping Problem MEC/GI

引用

algorithmICA 2010年第3期56卷 283-296页

作者： Wang, Jianxin Xie, Minzhu Chen, Jianer Hunan Normal Univ Coll Phys & Informat Sci Changsha 410081 Hunan Peoples R China Cent S Univ Sch Informat Sci & Engn Changsha 410083 Peoples R China Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA

Haplotypes play an important role in genetic association studies of complex diseases. Recently, computational techniques helping to determine human haplotypes were studied extensively. Given the genotype and the aligned single nucleotide polymorphism (SNP) fragments of an individual, Minimum Error Correction with Genotype Information (MEC/GI) is an important computational model to infer a pair of haplotypes compatible with the genotype by correcting minimum number of SNPs in the given SNP fragments. The MEC/GI problem has been proven NP-hard, for which there is no practical exact algorithm. Despite the rapid advances in molecular biological techniques, modern high-throughput sequencers cannot sequence directly a DNA fragment that contains more than 1200 nucleotide bases. With low SNP density, current available data reveal that the number k of SNP sites that a DNA fragment covers is usually smaller than 10. Based on the above fact, we develop a new dynamic programming algorithm with running time O(mk2 (k) +mlog m+mk), where m is the number of fragments. Since k is small in real biological applications, the algorithm is practical and efficient.

关键词： SNP (single nucleotide polymorphism) Haplotype Genotype NP-hardness parameterized algorithm

来源：评论

学校读者我要写书评

暂无评论

Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth

引用

algorithmICA 2011年第1期61卷 3-35页

作者： Blaeser, Markus Hoffmann, Christian Univ Saarland Fachbereich Informat D-66041 Saarbrucken Germany

We consider the multivariate interlace polynomial introduced by Courcelle (Electron. J. Comb. 15(1), 2008), which generalizes several interlace polynomials defined by Arratia, Bollobas, and Sorkin (J. Comb. Theory Ser. B 92(2):199-233, 2004) and by Aigner and van der Holst (Linear Algebra Appl., 2004). We present an algorithm to evaluate the multivariate interlace polynomial of a graph with n vertices given a tree decomposition of the graph of width k. The best previously known result (Courcelle, Electron. J. Comb. 15(1), 2008) employs a general logical framework and leads to an algorithm with running time f(k).n, where f(k) is doubly exponential in k. Analyzing the GF(2)-rank of adjacency matrices in the context of tree decompositions, we give a faster and more direct algorithm. Our algorithm uses 23k(2)+O(k).n arithmetic operations and can be efficiently implemented in parallel.

关键词： parameterized algorithm Tree decomposition Interlace polynomial Adjacency matrix Gaussian elimination

来源：评论

学校读者我要写书评

暂无评论

Voting and Bribing in Single-Exponential Time 34

Voting and Bribing in Single-Exponential Time

引用

34th Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Knop, Dusan Koutecky, Martin Mnich, Matthias Charles Univ Prague Dept Appl Math Prague Czech Republic Maastricht Univ Dept Quantitat Econ Maastricht Netherlands

ISBN: (纸本)9783959770286

We introduce a general problem about bribery in voting systems. In the R-MULTI-BRIBERY problem, the goal is to bribe a set of voters at minimum cost such that a desired candidate wins the manipulated election under the voting rule R. Voters assign prices for withdrawing their vote, for swapping the positions of two consecutive candidates in their preference order, and for perturbing their approval count for a candidate. As our main result, we show that R-MULTI-BRIBERY is fixed-parameter tractable parameterized by the number of candidates for many natural voting rules R, including Kemeny rule, all scoring protocols, maximin rule, Bucklin rule, fallback rule, SP-AV, and any Cl rule. In particular, our result resolves the parameterized of R-SwAP BRIBERY for all those voting rules, thereby solving a long-standing open problem and "Challenge #2" of the 9 Challenges in computational social choice by Bredereck et al. Further, our algorithm runs in single-exponential time for arbitrary cost;it thus improves the earlier double-exponential time algorithm by Dorn and Schlotter that is restricted to the unit-cost case for all scoring protocols, the maximin rule, and Bucklin rule.

关键词： parameterized algorithm swap bribery n-fold integer programming

来源：评论

学校读者我要写书评

暂无评论

On the Maximum Weight Minimal Separator 14th

On the Maximum Weight Minimal Separator

引用

14th Annual Conference on Theory and Applications of Models of Computation (TAMC)

作者： Hanaka, Tesshu Bodlaender, Hans L. van der Zanden, Tom C. Ono, Hirotaka Kyushu Univ Dept Econ Engn Higashi Ku 6-19-1 Hakozaki Fukuoka 8128581 Japan Univ Utrecht Dept Comp Sci POB 80-089 NL-3508 TB Utrecht Netherlands Eindhoven Univ Technol Dept Math & Comp Sci POB 513 NL-5600 MB Eindhoven Netherlands

ISBN: (纸本)9783319559117;9783319559100

Given an undirected and connected graph G = (V, E) and two vertices s, t is an element of V, a vertex subset S that separates s and t is called an s-t separator, and an s-t separator is called minimal if no proper subset of S separates s and t. In this paper, we consider finding a minimal s-t separator with maximum weight on a vertex-weighted graph. We first prove that this problem is NP-hard. Then, we propose an tw(O(tw))n-time deterministic algorithm based on tree decompositions. Moreover, we also propose an O*(9(tw).W-2)-time randomized algorithm to determine whether there exists a minimal s-t separator where W is its weight and tw is the treewidth of G.

关键词： parameterized algorithm Minimal separator Treewidth

来源：评论

学校读者我要写书评

暂无评论

FPT Approximation for Capacitated Sum of Radii 15

FPT Approximation for Capacitated Sum of Radii

引用

15th Innovations in Theoretical Computer Science Conference (ITCS)

作者： Jaiswal, Ragesh Kumar, Amit Yadav, Jatin IIT Delhi CSE Delhi India

ISBN: (纸本)9783959773096

We consider the capacitated clustering problem in general metric spaces where the goal is to identify k clusters and minimize the sum of the radii of the clusters (we call this the CAPACITATED k-sumRADii problem). We are interested in fixed-parameter tractable (FPT) approximation algorithms where the running time is of the form f (k) " poly(n), where f (k) can be an exponential function of k and n is the number of points in the input. In the uniform capacity case, Bandyapadhyay et al. recently gave a 4-approximation algorithm for this problem. Our first result improves this to an FPT 3-approximation and extends to a constant factor approximation for any Lp norm of the cluster radii. In the general capacities version, Bandyapadhyay et al. gave an FPT 15-approximation algorithm. We extend their framework to give an FPT (4-V13)-approximation algorithm for this problem. Our framework relies on a novel idea of identifying approximations to optimal clusters by carefully pruning points from an initial candidate set of points. This is in contrast to prior results that rely on guessing suitable points and building balls of appropriate radii around them. On the hardness front, we show that assuming the Exponential Time Hypothesis, there is a constant c> 1 such that any c-approximation algorithm for the non-uniform capacity version of this (kproblem requires running time 2(Omega) (k/polylog(k)).

关键词： Approximation algorithm parameterized algorithm clustering

来源：评论

学校读者我要写书评

暂无评论

Preemptive Scheduling of Equal-Length Jobs in Polynomial Time

引用

MATHEMATICS IN COMPUTER SCIENCE 2010年第1期3卷 73-84页

作者： Mertzios, George B. Unger, Walter Rhein Westfal TH Aachen Dept Comp Sci Ahornstr 55 D-52074 Aachen Germany

We study the preemptive scheduling problem of a set of n jobs with release times and equal processing times on a single machine. The objective is to minimize the sum of the weighted completion times Sigma(n)(i=1) w(i)C(i) of the jobs. We propose for this problem the first parameterized algorithm on the number k of different weights. The runtime of the proposed algorithm is O ((n/k + 1 )(k) n(8)) and hence, the problem is polynomially solvable for any fixed number k of different weights.

关键词： Machine scheduling Preemptive scheduling Equal-length jobs parameterized algorithm Polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

On Structural Parameterizations of the Matching Cut Problem 11th

On Structural Parameterizations of the Matching Cut Problem

引用

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

作者： Aravind, N. R. Kalyanasundaram, Subrahmanyam Kare, Anjeneya Swami IIT Hyderabad Dept Comp Sci & Engn Hyderabad India Univ Hyderabad Hyderabad Andhra Pradesh India

ISBN: (纸本)9783319711478;9783319711461

In an undirected graph, a matching cut is a partition of vertices into two sets such that the edges across the sets induce a matching. The matching cut problem is the problem of deciding whether a given graph has a matching cut. The matching cut problem can be expressed using a monadic second-order logic (MSOL) formula and hence is solvable in linear time for graphs with bounded tree -width. However, this approach leads to a running time of f (0,t)n (1), where 0 is the length of the MSOL formula, t is the tree-width of the graph and n is the number of vertices of the graph. In [Theoretical Computer Science, 2016], Kratsch and Le asked to give a single exponential algorithm for the matching cut problem with tree-width alone as the parameter. We answer this question by giving a 20(t)nc)(1) time algorithm. We also show the tractability of the matching cut problem when parameterized by neighborhood diversity and other structural parameters.

关键词： Matching cut Decomposable graphs parameterized algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：