排序方式: 共有32条查询结果,搜索用时 15 毫秒
1.
2.
Dekel Tsur 《Discrete Applied Mathematics》2007,155(10):1275-1293
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.
Janina A. Brenner Sándor P. Fekete Jan C. van der Veen 《Mathematical Methods of Operations Research》2009,69(2):281-296
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
汪长平 《高校应用数学学报(A辑)》1999,14(4):485-488
设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.
6.
Sascha Bachmann Matthias Reitzner 《Stochastic Processes and their Applications》2018,128(10):3327-3352
Concentration bounds for the probabilities and are proved, where is a median or the expectation of a subgraph count 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 F∩A 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.
J.M. McDonald 《Discrete Mathematics》2009,309(8):2077-2214
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. 相似文献