首页 | 本学科首页   官方微博 | 高级检索  
文章检索
  按 检索   检索词:      
出版年份:   被引次数:   他引次数: 提示:输入*表示无穷大
  收费全文   31篇
  免费   0篇
  国内免费   1篇
化学   1篇
数学   28篇
物理学   3篇
  2022年   1篇
  2021年   2篇
  2020年   2篇
  2018年   3篇
  2014年   1篇
  2013年   3篇
  2012年   1篇
  2011年   1篇
  2010年   1篇
  2009年   5篇
  2008年   1篇
  2007年   2篇
  2005年   1篇
  2002年   1篇
  2001年   1篇
  1999年   3篇
  1998年   1篇
  1993年   1篇
  1985年   1篇
排序方式: 共有32条查询结果,搜索用时 15 毫秒
1.
2.
We study the following problem: given a tree G and a finite set of trees H, find a subset O of the edges of G such that G-O does not contain a subtree isomorphic to a tree from H, and O has minimum cardinality. We give sharp boundaries on the tractability of this problem: the problem is polynomial when all the trees in H have diameter at most 5, while it is NP-hard when all the trees in H have diameter at most 6. We also show that the problem is polynomial when every tree in H has at most one vertex with degree more than 2, while it is NP-hard when the trees in H can have two such vertices.The polynomial-time algorithms use a variation of a known technique for solving graph problems. While the standard technique is based on defining an equivalence relation on graphs, we define a quasiorder. This new variation might be useful for giving more efficient algorithm for other graph problems.  相似文献   
3.
We consider a special case of the directed subgraph homeomorphism or topological minor problem, where the host graph has a specific regular structure. Given an acyclic directed pattern graph, we are looking for a host graph of minimal height which still allows for an embedding. This problem has applications in compiler design for certain coarse-grain reconfigurable architectures. In this application domain, the task is to simultaneously schedule, bind and route a so-called data-flow graph, where vertices represent operations and arcs stand for data dependencies between the operations, given an orthogonal grid structure of reconfigurable processing elements (PEs) that have restricted communication abilities. We show that the problem of simultaneously scheduling, binding and routing is NP-complete by describing a logic engine reduction from NAE-3-SAT. This result holds even when the input graph is a directed tree with maximum indegree two. We also give a |V|3/2-approximation algorithm. J. A. Brenner’s research supported by the DFG Research Center Matheon “Mathematics for key technologies”. J. C. van der Veen’s research supported by DFG Focus Program 1148, “Reconfigurable Architectures”, Grants FE 407/8-1 and FE 407/8-2.  相似文献   
4.
图中具有某种性质的子图   总被引:1,自引:0,他引:1  
设g和f是定义在图G的顶点集合V(G)上的整数值函数且对每个x∈V(G)都有0≤g(x)≤f(x)且g(x)和f(x)为偶数。本文证明了:若G是一个(mg+k-1,mf-k+1)-图,1≤k≤m,H是G中一个给定的有k条边的子图,则G存在一个子图R使得R有一个(g,f)-因子分解与H正交。  相似文献   
5.
关于k—覆盖图的一些新结果   总被引:1,自引:0,他引:1  
本文给出了一个图G是k-覆盖图的若干充分条件.  相似文献   
6.
Concentration bounds for the probabilities P(NM+r) and P(NM?r) are proved, where M is a median or the expectation of a subgraph count N associated with a random geometric graph built over a Poisson process. The lower tail bounds have a Gaussian decay and the upper tail inequalities satisfy an optimality condition. A remarkable feature is that the underlying Poisson process can have a.s. infinitely many points.The estimates for subgraph counts follow from tail inequalities for more general local Poisson U-statistics. These bounds are proved using recent general concentration results for Poisson U-statistics and techniques involving the convex distance for Poisson processes.  相似文献   
7.
贴片电阻表面缺陷自动识别方法   总被引:1,自引:0,他引:1  
贴片电阻生产过程中的缺陷主要依靠人工在显微镜下检测,速度慢、长期成本高、误检率高.针对贴片电阻单元具有排列整齐、结构简单、图像灰度级少的特点,在贴片电阻图像二值化、边缘提取、直线检测基础上,以相邻电阻单元的相关系数作为电阻缺陷判别依据,提出基于子图投影匹配的快速缺陷检测方法.采用主分量分析法压缩图像数据量,提取缺陷特征,以基于支持向量机对贴片电阻缺陷进行分类并建立实验系统.缺陷检测及识别实验表明,缺陷检测正确率为92.5oo,算法的快速性和识别准确度满足系统快速高精的要求.  相似文献   
8.
图的1-因子、f-因子和(g,f)-因子   总被引:5,自引:0,他引:5  
设G是一个图且有一个1-因子F,g和f是定义在V(G)上的非负整数值函数且对每个X∈V(G)有g(X)<f(X)≤dG(x),且f(v(G))为偶数.(i)若对每个xy∈F有f(x)=f(y)且G-{x,y}有一个(g,f)-因子,则G有一个(g,f)-因子;(ii)若对每个xy∈F有f(X)=f(y)且G-{X,y}有f-因子,则G有f-因子.  相似文献   
9.
Guoli Ding 《Discrete Mathematics》2009,309(5):1123-1134
An antichain A of a well-founded quasi-order Q is canonical if for every ideal F of Q, F has an infinite antichain if and only if FA is infinite. In this paper we characterize the obstructions to having a canonical antichain. As an application we show that, under the induced subgraph relation, the class of finite graphs does not have a canonical antichain. In contrast, this class does have a canonical antichain with respect to the subgraph relation.  相似文献   
10.
Let G be a multigraph with maximum degree Δ and maximum edge multiplicity μ. Vizing’s Theorem says that the chromatic index of G is at most Δ+μ. If G is bipartite its chromatic index is well known to be exactly Δ. Otherwise G contains an odd cycle and, by a theorem of Goldberg, its chromatic index is at most , where go denotes odd-girth. Here we prove that a connected G achieves Goldberg’s upper bound if and only if G=μCgo and (go−1)∣2(μ−1). The question of whether or not G achieves Vizing’s upper bound is NP-hard for μ=1, but for μ≥2 we have reason to believe that this may be answerable in polynomial time. We prove that, with the exception of μK3, every connected G with μ≥2 which achieves Vizing’s upper bound must contain a specific dense subgraph on five vertices. Additionally, if Δμ2, we prove that G must contain K5, so G must be nonplanar. These results regarding Vizing’s upper bound extend work by Kierstead, whose proof technique influences us greatly here.  相似文献   
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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