首页 | 本学科首页   官方微博 | 高级检索  
文章检索
  按 检索   检索词:      
出版年份:   被引次数:   他引次数: 提示:输入*表示无穷大
  收费全文   30篇
  免费   0篇
化学工业   2篇
轻工业   1篇
自动化技术   27篇
  2016年   4篇
  2015年   3篇
  2014年   2篇
  2013年   4篇
  2012年   4篇
  2011年   2篇
  2010年   2篇
  2009年   1篇
  2008年   2篇
  2007年   2篇
  2002年   1篇
  1994年   1篇
  1991年   2篇
排序方式: 共有30条查询结果,搜索用时 31 毫秒
1.
2.
3.
The notion of distance constrained graph labelings, motivated by the Frequency Assignment Problem, reads as follows: A mapping from the vertex set of a graph G=(V,E) into an interval of integers {0,…,k} is an L(2,1)-labeling of G of span k if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbor are mapped onto distinct integers. It is known that for any fixed k≥4, deciding the existence of such a labeling is an NP-complete problem. We present exact exponential time algorithms that are faster than the naive O *((k+1) n ) algorithm that would try all possible mappings. The improvement is best seen in the first NP-complete case of k=4, where the running time of our algorithm is O(1.3006 n ). Furthermore we show that dynamic programming can be used to establish an O(3.8730 n ) algorithm to compute an optimal L(2,1)-labeling.  相似文献   
4.
We study the problem of computing Nash equilibria in a two-player normal form (bimatrix) game from the perspective of parameterized complexity. Recent results proved hardness for a number of variants, when parameterized by the support size. We complement those results, by identifying three cases in which the problem becomes fixed-parameter tractable. Our results are based on a graph-theoretic representation of a bimatrix game, and on applying graph-theoretic tools on this representation.  相似文献   
5.
6.
7.
Given an n-node edge-weighted graph and a subset of k terminal nodes, the NP-hard (weighted) Steiner tree problem is to compute a minimum-weight tree which spans the terminals. All the known algorithms for this problem which improve on trivial O(1.62 n )-time enumeration are based on dynamic programming, and require exponential space. Motivated by the fact that exponential-space algorithms are typically impractical, in this paper we address the problem of designing faster polynomial-space algorithms. Our first contribution is a simple O((27/4) k n O(logk))-time polynomial-space algorithm for the problem. This algorithm is based on a variant of the classical tree-separator theorem: every Steiner tree has a node whose removal partitions the tree in two forests, containing at most 2k/3 terminals each. Exploiting separators of logarithmic size which evenly partition the terminals, we are able to reduce the running time to $O(4^{k}n^{O(\log^{2} k)})$ . This improves on trivial enumeration for roughly k<n/3, which covers most of the cases of practical interest. Combining the latter algorithm (for small k) with trivial enumeration (for large k) we obtain a O(1.59 n )-time polynomial-space algorithm for the weighted Steiner tree problem. As a second contribution of this paper, we present a O(1.55 n )-time polynomial-space algorithm for the cardinality version of the problem, where all edge weights are one. This result is based on a improved branching strategy. The refined branching is based on a charging mechanism which shows that, for large values of k, convenient local configurations of terminals and non-terminals exist. The analysis of the algorithm relies on the Measure & Conquer approach: the non-standard measure used here is a linear combination of the number of nodes and number of non-terminals. Using a recent result in Nederlof (International colloquium on automata, languages and programming (ICALP), pp. 713–725, 2009), the running time can be reduced to O(1.36 n ). The previous best algorithm for the cardinality case runs in O(1.42 n ) time and exponential space.  相似文献   
8.
9.
A simple method for dipcoating porous reticular carbon foam with aluminum oxide thin-film coatings is presented. Weight gain versus temperature and number of dipcoatings is presented along with scanning electron micrographs of uniform, adherent alumina thin films. Composite foam structures of up to 57% alumina have been prepared.  相似文献   
10.
The Subset Feedback Vertex Set problem takes as input a pair (G,S), where G=(V,E) is a graph with weights on its vertices, and S?V. The task is to find a set of vertices of total minimum weight to be removed from G, such that in the remaining graph no cycle contains a vertex of S. We show that this problem can be solved in time O(1.8638 n ), where n=|V|. This is a consequence of the main result of this paper, namely that all minimal subset feedback vertex sets of a graph can be enumerated in time O(1.8638 n ).  相似文献   
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号