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

parameterized computation and complexity: A new approach dealing with NP-hardness

JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 2005年第1期20卷 18-37页

作者： Chen, JE Cent S Univ Coll Informat Sci & Engn Changsha 410083 Peoples R China

The theory of parameterized computation and complexity is a recently developed subarea in theoretical computer science. The theory is aimed at practically solving a large number of computational problems that are theoretically intractable. The theory is based on the observation that many intractable computational problems in practice are associated with a parameter that varies within a small or moderate range. Therefore, by taking the advantages of the small parameters, many theoretically intractable problems can be solved effectively and practically. On the other hand, the theory of parameterized computation and complexity has also offered powerful techniques that enable us to derive strong computational lower bounds for many computational problems, thus explaining why certain theoretically tractable problems cannot be solved effectively and practically. The theory of parameterized computation and complexity has found wide applications in areas such as database systems, programming languages, networks, VLSI design, parallel and distributed computing, computational biology, and robotics. This survey gives an overview on the fundamentals, algorithms, techniques, and applications developed in the research of parameterized computation and complexity. We will also report the most recent advances and excitements, and discuss further research directions in the area.

关键词： algorithm computational complexity NP-completeness parameterized computation approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

STUDY OF PROTEIN STRUCTURE ALIGNMENT PROBLEM IN parameterized computation

STUDY OF PROTEIN STRUCTURE ALIGNMENT PROBLEM IN PARAMETERIZE...

引用

International Conference on Bioinformatics Models, Methods and Algorithms (BIOINFORMATICS)

作者： Ashby, Cody Wang, Kun Cramer, Carole L. Huang, Xiuzhen Arkansas State Univ MBS PhD Program Jonesboro AR USA

ISBN: (纸本)9789898425904

Motivated by the practical application of protein structure-structure alignment, we have studied the problem of maximum common subgraph within the framework of parameterized complexity. We investigated the lower bound for the exact algorithms of the problem. We proved it unlikely that there is an algorithm of time p(n,m) * k(o(m)) for the problem, where p is a polynomial function, k is a parameter of map width, and m and n are the numbers of vertices of the the two graphs respectively. In consideration of the upper bound of p(n,m)*k(m) based on the brute-force approach, our lower bound result is asymptotically tight. Although the algorithm with the running time p(n,m) k(m) could not be significantly improved from our lower bound result, it is still possible to develop efficient algorithms or the practical application of the protein structure-structure alignment. We developed an efficient algorithm integrating the color coding method and parameterized computation for identifying the maximum common subgraph of two prot structure graphs. We have applied the algorithm to protein structure-structure alignment and conducted experimental testing of more than 600 protein pairs. Our parameterized approach shows improvement in structure alignment efficiency and will be very useful for structure comparisons of proteins with large sizes.

关键词： Protein structure-structure alignment Color coding parameterized computation Maximum common subgraph

来源：评论

学校读者我要写书评

暂无评论

On Unknown Small Subsets and Implicit Measures: New Techniques for parameterized Algorithms

引用

Journal of Computer Science & Technology 2014年第5期29卷 870-878页

作者：陈建二冯启龙 School of Information Science and Engineering Central South University Department of Computer Science Texas A&M UniversityTexas 77843-3112 U.S.A.

parameterized computation is a recently proposed alternative approach to dealing with NP-hard *** efficient parameterized algorithms has become a very active research area in the current research in theoretical computer science. In this paper, we investigate a number of new algorithmic techniques that were proposed and initiated by ourselves in our research in parameterized computation. The techniques have proved to be very useful and promising,and have led to improved parameterized algorithms for many well-known NP-hard problems.

关键词： parameterized computation randomized method implicit branching

来源：评论

学校读者我要写书评

暂无评论

Nearly Time-Optimal Kernelization Algorithms for the Line-Cover Problem with Big Data

引用

ALGORITHMICA 2024年第8期86卷 2448-2478页

作者： Chen, Jianer Huang, Qin Kanj, Iyad Xia, Ge Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA DePaul Univ Sch Comp Chicago IL USA Lafayette Coll Dept Comp Sci Easton PA USA

Based on well-known complexity theory conjectures, any polynomial-time kernelization algorithm for the NP-hard Line-Cover problem produces a kernel of size Omega(k2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega (k<^>2)$$\end{document}, where k is the size of the sought line cover. Motivated by the current research in massive data processing, we study the existence of kernelization algorithms with limited space and time complexity for Line-Cover. We prove that every kernelization algorithm for Line-Cover takes time Omega(nlogk+k2logk)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega (n \log k + k<^>2 \log k)$$\end{document}, and present a randomized kernelization algorithm for Line-Cover that produces a kernel of size bounded by k2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k<^>2$$\end{document}, and runs in time O(nlogk+k2(logkloglogk)2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}}(n \log k + k<^>2 (\log k \log \log k)<^>2)$$\end{document} and space O(k2log2k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}}(k<^>2\log <^>{2} k

关键词： Line cover Kernelization algorithm NP-complete geometric problem parameterized computation

来源：评论

学校读者我要写书评

暂无评论

On Feedback Vertex Set: New Measure and New Structures

引用

ALGORITHMICA 2015年第1期73卷 63-86页

作者： Cao, Yixin Chen, Jianer Liu, Yang Hong Kong Polytech Univ Dept Comp Hong Kong Hong Kong Peoples R China Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA Texas A&M Univ Supercomp Facil College Stn TX 77845 USA

We present a new parameterized algorithm for the feedback vertex set problem (fvs) on undirected graphs. We approach the problem by considering a variation of it, the disjoint feedback vertex set problem (disjoint-fvs), which finds a feedback vertex set of size that has no overlap with a given feedback vertex set of the graph . We develop an improved kernelization algorithm for disjoint-fvs and show that disjoint-fvs can be solved in polynomial time when all vertices in have degrees upper bounded by three. We then propose a new branch-and-search process on disjoint-fvs, and introduce a new branch-and-search measure. The process effectively reduces a given graph to a graph on which disjoint-fvs becomes polynomial-time solvable, and the new measure more accurately evaluates the efficiency of the process. These algorithmic and combinatorial studies enable us to develop an -time parameterized algorithm for the general fvs problem, improving all previous algorithms for the problem.

关键词： Disjoint feedback vertex set parameterized computation Kernlization Measure and bound Cubic graphs Cographicmatroid Matroid intersection problem

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity and improved inapproximability for computing the largest j-simplex in a V-polytope

引用

INFORMATION PROCESSING LETTERS 2006年第1期100卷 8-13页

作者： Koutis, Ioannis Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA

We consider the problem of computing the squared volume of the largest j-simplex contained in an n-dimensional polytope presented by its vertices (a V-polytope). We show that the related decision problem is W[I]-complete, with respect to the parameter j. We also improve the constant inapproximability factor given in [A. Packer, Polynomial-time approximation of largest simplices in V-polytopes, Discrete Appl. Math. 134 (1-3) (2004) 213-237], by showing that there are constants mu < 1, c > 1 such that it is NP-hard to approximate within a factor of c(mu n) the volume of the largest [mu n]-simplex contained in an n-dimensional polytope with O(n) vertices. (c) 2006 Elsevier B.V. All rights reserved.

关键词： computational complexity computational geometry inapproximability parameterized computation

来源：评论

学校读者我要写书评

暂无评论

Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree

引用

INFORMATION AND computation 2017年 252卷 187-200页

作者： Li, Wenjun Cao, Yixin Chen, Jianer Wang, Jianxin Cent S Univ Sch Informat Sci & Engn Changsha Hunan Peoples R China Changsha Univ Sci & Technol Sch Comp & Commun Engn Hunan Prov Key Lab Intelligent Proc Big Data Tran Changsha Hunan Peoples R China Hong Kong Polytech Univ Dept Comp Hong Kong Hong Kong Peoples R China Texas A&M Univ Dept Comp Sci & Engn College Stn TX USA

The maximum internal spanning tree problem asks for a spanning tree of a given graph that has the maximum number of internal vertices among all spanning trees of this graph. In its parameterized version, we are interested in whether the graph has a spanning tree with at least k internal vertices. Fomin et al. (2013) [4] crafted a very ingenious reduction rule, and showed that a simple application of this rule is sufficient to yield a 3k-vertex kernel, implying an 0*(8(k))-time parameterized algorithm. Using depth-2 local search, Knauer and Spoerhase (2015) [9] developed a (5/3)-approximation algorithm for the optimization version. We try deeper local search: We conduct a thorough combinatorial analysis on the obtained spanning trees and explore their algorithmic consequences. We first observe that from the spanning tree obtained by depth-3 local search, one can easily find a reducible structure and apply the reduction rule of Fomin et al. This gives an improved kernel of 2k vertices, and as a by-product, a deterministic algorithm running in time 0*(4(k)). We then go even deeper by considering the spanning tree obtained by depth-5 local search. It is shown that the number of internal vertices of this spanning tree is at least 2/3 of the maximum number a spanning tree can have, thereby delivering an improved approximation algorithm with ratio 1.5 for the problem. (C) 2016 Elsevier Inc. All rights reserved.

关键词： Maximum internal spanning tree parameterized computation Local search

来源：评论

学校读者我要写书评

暂无评论

Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2003年第4期67卷 833-847页

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

Motivated by the research in reconfigurable memory array structures, this paper studies the complexity and algorithms for the constrained minimum vertex cover problem on bipartite graphs (MIN-CVCB) defined as follows: given a bipartite graph G = (V, E) with vertex bipartition V = U boolean OR L and two integers k(u) and k(l), decide whether there is a minimum vertex cover in G with at most k(u) vertices in U and at most k(l) vertices in L. It is proved in this paper that the MIN-CVCB problem is NP-complete. This answers a question posed by Hasan and Liu. A parameterized algorithm is developed for the problem, in which classical results in matching theory and recently developed techniques in parameterized computation theory are nicely combined and extended. The algorithm runs in time O(1.26(ku + kl) + (k(u) + k(l))\G\) and significantly improves previous algorithms for the problem. (C) 2003 Elsevier Inc. All rights reserved.

关键词： vertex cover bipartite graph graph matching parameterized computation

来源：评论

学校读者我要写书评

暂无评论

On parameterized intractability: Hardness and completeness

引用

COMPUTER JOURNAL 2008年第1期51卷 39-59页

作者： Chen, Jianer Meng, Jie Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA

We study the theory and techniques developed in the research of parameterized intractability, emphasizing on parameterized hardness and completeness that imply (stronger) computational lower bounds for natural computational problems. Moreover, the fundamentals of the structural properties in parameterized complexity theory, relationships to classical complexity theory and more recent developments in the area are also introduced.

关键词： parameterized computation fixed parameter tractability W-hierarchy exact algorithm

来源：评论

学校读者我要写书评

暂无评论

An efficient parameterized algorithm for m-set packing

引用

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC 2004年第1期50卷 106-117页

作者： Jia, WJ Zhang, CL Chen, J City Univ Hong Kong Dept Comp Engn & IT Hong Kong Hong Kong Peoples R China Jinan Univ Dept Math Guangzhou 510632 Peoples R China Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA

We present an efficient parameterized algorithm solving the Set Packing problem, in which we assume that the size of the sets is bounded by m. In particular, if the size m of the sets is bounded by a constant, then our algorithm is fixed-parameter tractable. For example, if the size of the sets is bounded by 3, then our algorithm runs in time O((5.7k)(k)n). (C) 2003 Elsevier Inc. All rights reserved.

关键词： parameterized computation set packing exact algorithm NP-hard problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：