 首页 | 本学科首页 官方微博 | 高级检索

 按 中文标题 英文标题 中文关键词 英文关键词 中文摘要 英文摘要 作者中文名 作者英文名 单位中文名 单位英文名 基金中文名 基金英文名 杂志中文名 杂志英文名 栏目英文名 栏目英文名 DOI 责任编辑 分类号 杂志ISSN号 检索 检索词:

 收费全文 523篇 国内免费 4篇 完全免费 102篇
 自动化技术 629篇
 2019年 1篇 2018年 2篇 2017年 4篇 2016年 9篇 2015年 14篇 2014年 19篇 2013年 9篇 2012年 16篇 2011年 44篇 2010年 29篇 2009年 73篇 2008年 102篇 2007年 34篇 2006年 40篇 2005年 42篇 2004年 44篇 2003年 35篇 2002年 32篇 2001年 16篇 2000年 7篇 1999年 9篇 1998年 8篇 1997年 11篇 1996年 4篇 1995年 5篇 1994年 3篇 1993年 1篇 1992年 4篇 1991年 1篇 1990年 4篇 1989年 4篇 1988年 2篇 1985年 1篇

1.

2.
Approximation Algorithms for Connected Dominating Sets   总被引：37，自引：0，他引：37
S. Guha  S. Khuller 《Algorithmica》1998,20(4):374-387
The dominating set problem in graphs asks for a minimum size subset of vertices with the following property: each vertex is required to be either in the dominating set, or adjacent to some vertex in the dominating set. We focus on the related question of finding a connected dominating set of minimum size, where the graph induced by vertices in the dominating set is required to be connected as well. This problem arises in network testing, as well as in wireless communication. Two polynomial time algorithms that achieve approximation factors of 2H(Δ)+2 and H(Δ)+2 are presented, where Δ is the maximum degree and H is the harmonic function. This question also arises in relation to the traveling tourist problem, where one is looking for the shortest tour such that each vertex is either visited or has at least one of its neighbors visited. We also consider a generalization of the problem to the weighted case, and give an algorithm with an approximation factor of (c n +1) \ln n where c n ln k is the approximation factor for the node weighted Steiner tree problem (currently c n = 1.6103 ). We also consider the more general problem of finding a connected dominating set of a specified subset of vertices and provide a polynomial time algorithm with a (c+1) H(Δ) +c-1 approximation factor, where c is the Steiner approximation ratio for graphs (currently c = 1.644 ). Received June 22, 1996; revised February 28, 1997.  相似文献
3.

4.

5.

6.
We study the maximum integral multicommodity flow problem and the minimum multicut problem restricted to trees. This restriction is quite rich and contains as special cases classical optimization problems such as matching and vertex cover for general graphs. It is shown that both the maximum integral multicommodity flow and the minimum multicut problem are NP-hard and MAX SNP-hard on trees, although the maximum integral flow can be computed in polynomial time if the edges have unit capacity. We present an efficient algorithm that computes a multicut and integral flow such that the weight of the multicut is at most twice the value of the flow. This gives a 2-approximation algorithm for minimum multicut and a 1/2-approximation algorithm for maximum integral multicommodity flow in trees.  相似文献
7.

8.
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.  相似文献
9.

10.

 设为首页 | 免责声明 | 关于勤云 | 加入收藏 Copyright©北京勤云科技发展有限公司  京ICP备09084417号