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

Multicut in trees viewed through the eyes of vertex cover

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2012年第5期78卷 1637-1650页

作者： Chen, Jianer Fan, Jia-Hao Kanj, Iyad Liu, Yang Zhang, Fenghui DePaul Univ Chicago IL 60604 USA Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA Univ Texas Pan Amer Dept Comp Sci Edinburg TX 78539 USA Google Kirkland Kirkland WA 98033 USA

We take a new look at the multicut problem in trees, denoted MULTICUT ON TREES henceforth, through the eyes of the VERTEX COVER problem. This connection, together with other techniques that we develop, allows us to give an upper bound of O(k(3)) on the kernel size for MULTICUT ON TREES, significantly improving the O(k(6)) upper bound given by Bousquet et al. We exploit this connection further to present a parameterized algorithm for MULTICUT ON TREES that runs in time O*(rho(k)), where rho = (root 5 + 1)/2 approximate to 1.618. This improves the previous (time) upper bound of O*(2(k)), given by Guo and Niedermeier, for the problem. (C) 2012 Elsevier Inc. All rights reserved.

关键词： parameterized complexity Kernelization parameterized algorithms Multicut

来源：评论

学校读者我要写书评

暂无评论

Fixed-parameter algorithms in phylogenetics

引用

COMPUTER JOURNAL 2008年第1期51卷 79-101页

作者： Gramm, Jens Nickelsen, Arfst Tantau, Till Med Univ Lubeck Inst Theoret Informat Lubeck Germany Univ Tubingen Wilhelm Schickard Inst Informat D-72074 Tubingen Germany

We survey the use of fixed-parameter algorithms in the field of phylogenetics, which is the study of evolutionary relationships. The central problem in phylogenetics is the reconstruction of the evolutionary history of biological species, but its methods also apply to linguistics, philology or architecture. A basic computational problem is the reconstruction of a likely phylogeny ( genealogical tree) for a set of species based on observed differences in the phenotype like color or form of limbs, based on differences in the genotype like mutated nucleotide positions in the DNA sequence, or based on given partial phylogenies. Ideally, one would like to construct socalled perfect phylogenies, which arise from a very simple evolutionary model, but in practice one must often be content with phylogenies whose 'distance from perfection' is as small as possible. The computation of phylogenies has applications in seemingly unrelated areas such as genomic sequencing and finding and understanding genes. The numerous computational problems arising in phylogenetics often are NP-complete, but for many natural parametrizations they can be solved using fixed-parameter algorithms.

关键词： bioinformatics phylogenetics algorithms parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Packing paths: Recycling saves time

引用

DISCRETE APPLIED MATHEMATICS 2013年第12期161卷 1686-1698页

作者： Binkele-Raible, Daniel Fernau, Henning Univ Trier FB Abt Informat 4 D-54286 Trier Germany

We consider packing problems in graphs under a parameterized perspective. Starting from a maximal path packing P of size j we use extremal arguments for determining how many vertices of P appear in a path packing of size j + 1. Generally, one can re-use 2j vertices of j paths of length three, four and five. This is improved to 3j, 2.5j and 3j vertices. (c) 2013 Published by Elsevier B.V.

关键词： parameterized algorithms Graphs Packings Extremal graph theory

来源：评论

学校读者我要写书评

暂无评论

Parametrized Complexity of Length-Bounded Cuts and Multi-cuts 12

Parametrized Complexity of Length-Bounded Cuts and Multi-cut...

引用

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

作者： Dvorak, Pavel Knop, Dusan Charles Univ Prague Dept Appl Math CR-11800 Prague Czech Republic

ISBN: (纸本)9783319171425;9783319171418

We show that the minimal length-bounded L-cut can be computed in linear time with respect to L and the tree-width of the input graph as parameters. We derive an FPT algorithm for a more general multi-commodity length bounded cut problem when parameterized by the number of terminals also. For the former problem we show a W[1]-hardness result when the parameterization is done by the path-width only (instead of the tree-width).

关键词： Length bounded cuts parameterized algorithms W-hardness

来源：评论

学校读者我要写书评

暂无评论

Complexity of the Steiner Network Problem with Respect to the Number of Terminals 36

Complexity of the Steiner Network Problem with Respect to th...

引用

36th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Eiben, Eduard Knop, Dusan Panolan, Fahad Suchy, Ondrej Univ Bergen Dept Informat Bergen Norway TU Berlin Fac 4 Algorithm & Computat Complex Berlin Germany Czech Tech Univ Fac Informat Technol Dept Theoret Comp Sci Prague Czech Republic

ISBN: (纸本)9783959771009

In the Directed Steiner Network problem we are given an arc-weighted digraph G, a set of terminals T subset of V (G) with vertical bar T vertical bar = q, and an (unweighted) directed request graph R with V (R) = T. Our task is to output a subgraph H subset of G of the minimum cost such that there is a directed path from s to t in H for all st is an element of A(R). It is known that the problem can be solved in time vertical bar V (G)vertical bar(O(vertical bar A(R)vertical bar)) [Feldman&Ruhl, SIAM J. Comput. 2006] and cannot be solved in time vertical bar V (G)vertical bar(o(vertical bar A(R)vertical bar)) even if G is planar, unless the Exponential-Time Hypothesis (ETH) fails [Chitnis et al., SODA 2014]. However, the reduction (and other reductions showing hardness of the problem) only shows that the problem cannot be solved in time vertical bar V (G)vertical bar(o(q)), unless ETH fails. Therefore, there is a significant gap in the complexity with respect to q in the exponent. We show that Directed Steiner Network is solvable in time f(q) center dot vertical bar V (G)vertical bar(O(cg center dot q)), where cg is a constant depending solely on the genus of G and f is a computable function. We complement this result by showing that there is no f(q) center dot vertical bar V (G)vertical bar(o(q2 / log q)) algorithm for any function f for the problem on general graphs, unless ETH fails.

关键词： Directed Steiner Network Planar Graphs parameterized algorithms Bounded Genus Exponential Time Hypothesis

来源：评论

学校读者我要写书评

暂无评论

Improved exact algorithms for M_AX-S_AT 5

引用

5th Latin American Symposium on Theoretical Informatics (LATIN 2002)

作者： Chen, JE Kanj, IA Depaul Univ Sch CTI Chicago IL 60604 USA Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA

ISBN: (纸本)3540434003

In this paper, we present improved exact and parameterized algorithms for the maximum satisfiability problem. In particular, we give an algorithm that computes a truth assignment for a boolean formula F satisfying the maximum number of clauses in time O(1.3247(m)\F\), where m is the number of clauses in F, and \F\ is the sum of the number of literals appearing in each clause in F. Moreover, given a parameter k, we give an O(1.3695(k) + \F\) parameterized algorithm that decides whether a truth assignment for F satisfying at least k clauses exists. Both algorithms improve the previous best algorithms by Bansal and Raman for the problem. (C) 2004 Elsevier B.V. All rights reserved.

关键词： maximum satisfiability exact algorithms parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Contraction checking in graphs on surfaces

Contraction checking in graphs on surfaces

引用

29th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Kaminski, Marcin Thilikos, Dimitrios M. Univ Libre Bruxelles Dept Informat Brussels Belgium Univ Athens Dept Math Athens 11528 Greece

ISBN: (纸本)9783939897354

The CONTRACTION CHECKING problem asks, given two graphs H and G as input, whether H can be obtained from G by a sequence of edge contractions. Contraction Checking remains NP-complete, even when H is fixed. We show that this is not the case when G is embeddable in a surface of fixed Euler genus. In particular, we give an algorithm that solves Contraction Checking in f(h, g) . |V (G)|(3) steps, where h is the size of H and g is the Euler genus of the input graph G.

关键词： Surfaces Topological Minors Contractions parameterized algorithms Linkages

来源：评论

学校读者我要写书评

暂无评论

A Note on Vertex Cover in Graphs with Maximum Degree 3

A Note on Vertex Cover in Graphs with Maximum Degree 3

引用

16th Annual International Computing and Combinatorics Conference

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

ISBN: (纸本)9783642140303

We show that the k-Vertex Cover problem in degree-3 graphs can be solved in O*(1.1616(k)) time, which improves previous results of O*(1.1940(k)) by Chen, Kanj and Xia and O*(1.1864(k)) by Razgon. In this paper, we will present a new way to analyze algorithms for the problem. We use r = k - 2/5n to measure the size of the search tree, and then get a simple O(1.6651(k-2/5n0))-time algorithm, where no is the number of vertices with degree >= 2 in the graph. Combining this result with fast algorithms for the Maximum Independent Set problem in degree-3 graphs, we improve the upper bound for the k-Vertex Cover problem in degree-3 graphs.

关键词： parameterized algorithms Vertex Cover Independent Set Sparse Graphs

来源：评论

学校读者我要写书评

暂无评论

Dynamic Programming for Graphs on Surfaces

Dynamic Programming for Graphs on Surfaces

引用

37th International Colloquium on Automata, Languages and Programming

作者： Rue, Juanjo Sau, Ignasi Thilikos, Dimitrios M. Ecole Polytech Lab Informat F-91128 Palaiseau France Dept Comp Sci Technion Haifa Israel Natl & Kapodistrian Univ Athens Dept Mat Athens Greece

ISBN: (纸本)9783642141645

We provide a framework for the design and analysis of dynamic programming algorithms for surface-embedded graphs on n vertices and branchwidth at most k. Our technique applies to general families of problems where standard dynamic programming runs in 2(O(*** k)) n steps. Our approach combines tools from topological graph theory and analytic combinatorics. In particular, we introduce a new type of branch decomposition called surface cut decomposition;capturing how partial solutions can be arranged on a surface. Then we use singularity analysis over expressions obtained by the symbolic method to prove that partial solutions can be represented by a single-exponential (in the branchwidth k) number of configurations. This proves that, when applied on surface cut decompositions, dynamic programming runs in 2(O(k)) . n steps. That way, we considerably extend the class of problems that can be solved in running times with a single-exponential dependence on branchwidth and unify/improve all previous results in this direction.

关键词： analysis of algorithms parameterized algorithms analytic combinatorics graphs on surfaces branchwidth dynamic programming polyhedral embeddings symbolic method non-crossing partitions

来源：评论

学校读者我要写书评

暂无评论

Answer Set Solving with Bounded Treewidth Revisited 14th

Answer Set Solving with Bounded Treewidth Revisited

引用

14th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR)

作者： Fichte, Johannes K. Hecher, Markus Morak, Michael Woltran, Stefan TU Wien Inst Informat Syst Vienna Austria

ISBN: (纸本)9783319616605;9783319616599

parameterized algorithms are a way to solve hard problems more efficiently, given that a specific parameter of the input is small. In this paper, we apply this idea to the field of answer set programming (ASP). To this end, we propose two kinds of graph representations of programs to exploit their treewidth as a parameter. Treewidth roughly measures to which extent the internal structure of a program resembles a tree. Our main contribution is the design of parameterized dynamic programming algorithms, which run in linear time if the treewidth and weights of the given program are bounded. Compared to previous work, our algorithms handle the full syntax of ASP. Finally, we report on an empirical evaluation that shows good runtime behaviour for benchmark instances of low treewidth, especially for counting answer sets.

关键词： parameterized algorithms Tree decompositions

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：