首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 140 毫秒
1.
林政宽  赵源  樊建席  程宝雷 《计算机科学》2017,44(6):94-96, 107
在计算机互连网络中,完全独立生成树在信息的可靠传输、并行传输、安全分发等方面具有重要的作用。假设图G中存在n棵生成树T1,T2,…,Tn,若对于图G中任意两个顶点u和v,满足u和v之间的路径在这n棵树中都是顶点不相交的,则称这n棵树为完全独立生成树(CISTs)。在2015年,Chang等人证明了对于包含n(n≥6)个顶点的任意图G,如果图G的最小顶点度数至少为n-2,那么,G中存在至少 n/3 棵CISTs[1]。在Chang等人的基础上,文中继续深入研究了图G中顶点度数和CISTs的棵数之间的关系。对于包含n(n≥5) 个顶点的任意图G,假设图G的最小顶点度数至少为n-2,得出度数为n-2的顶点的个数、度数为n-1的顶点的个数与图G中CISTs的棵数之间关系的推导等式,并证明了其正确性,从而改进了文献[1]中的结果。  相似文献   

2.
研究内部节点受限的最小生成树问题:给定一个赋权无向完全图G=(V,E),假定w:E→R~+为边集E的权重函数且满足三角不等式,给定点集V的一个子集R(RV),目标是寻找图G的一个满足R中的点皆为内部顶点的权重最小的生成树。由于该问题是NP-困难的,提出了一个伪多项式时间最优算法,设计了一个近似比为2的多项式时间近似算法,并且给出例子以说明该近似比是紧的。  相似文献   

3.
建立了中继网络资源复用问题的图论模型,依据该模型设计了自适应资源复用调度算法ARRS(adaptive resource reuse scheduling),以提高中继网络资源利用率.由于ARRS算法的核心步骤涉及顶加权图G(V,E,W)的染色,是NP-hard问题,为此给出了求解最优资源复用约束的顶加权图染色的近似算法ARRS_Greedy.该算法被证明具有时间复杂度O(|V|2),近似比为?(Δ+1)/2?(Δ表示图G顶点度数的最大值).该近似比是紧的.仿真分析验证了近似算法ARRS_Greedy在应用中取得了与最优解非常接近的性能,证明了ARRS算法能够动态适应网络状态变化,因而与现有算法相比大幅度提高了系统容量.  相似文献   

4.
马俊  朱洪 《计算机科学》2006,33(1):220-222
连通支配集问题在网络广播上有着广泛的应用,本文引入测度函数的概念,提出了带测度函数的连通支配集问题(CDS(F)),使得它具有更广的应用范围。文中首先给出问题的形式定义,证明了它在各种情形下的NP完全性,并给出多项式时间的近似算法,它的近似度为Ln△+3(△为图中顶点的最大度数)。  相似文献   

5.
设G是一个图,f是定义在V(G)上的整数值函数,且对坌x∈V(G),有2k≤f(x),设H1,H2,…,Hk是G的k个顶点不相交的子图,且|E(Hi)|=m,1≤i≤k,证明了每个(0,mf-m+1)图有一个(0,f)因子分解正交于Hi(i=1,2,…,k)。  相似文献   

6.
图◢G=(V,E)的一个支配集DV是一个顶点子集,使得图中每一个顶点要么在D中,要么至少与D中的一个顶点相连。连通支配集问题是找到一个顶点数最小的支配集S,并且S的导出子图G[S]是连通图。◣该问题是一个经典的NP难问题,可应用于连通设施选址、自适应网络等领域。针对无向图中连通支配集问题,仔细分析该问题的图结构性质,挖掘出若干有效的约简规则和分支规则,设计了一个分支搜索算法,并采用了测量治之方法分析算法的运行时间,最终得到了一个运行时间复杂◢度为O*△(1.93n△)的精确◣算法。  相似文献   

7.
图G=(V,E)上的混合支配集D是由图G中的顶点和边组成的集合,因此对于图G中的任意一条边或一个顶点,若其不在D中,则其必须与D中某条边或某个顶点相邻。混合支配问题是在一个图中找到一个基数最小的混合支配集。混合支配问题是图顶点支配问题和边支配问题的混合,在实际生活中有着许多应用,最近在算法中也备受关注。混合支配问题在一般图上是NP完全的。带权混合支配问题则是混合支配问题的一个自然推广,其将图中的点和边以不同权重进行区分。令图中所有点的权重均为wv,所有边的权重均为we,带权混合支配问题则要求寻找一个混合支配集使得其点和边的权重之和达到最小。尽管针对混合支配问题已存在一个简单2倍近似算法,但是对带权混合支配问题的近似算法的研究进展却非常缓慢。在点的权重不大于边的权重的情况下,文中给出了带权混合支配问题的一个3倍近似算法。  相似文献   

8.
计算具有较小度的生成树是算法与复杂性研究的一个基本问题,同时在网络设计等领域具有重要应用.给定具有n个顶点的有向无环图G=(V,E)和根顶点r∈ V,最小度生成树问题欲求一棵以r为根的生成树T,使得在G的所有以r为根的生成树中T的最大度最小.给出该问题的一种迭代的多项式时间近似算法.该算法所求树的度不超过△*+1,其中△*为某一最优树的度.算法的时间复杂度为O(n2logn),其中n为顶点数目.算法没有运用过多的枚举,其实际运行时间要快得多.  相似文献   

9.
数据中心网络设计的新趋势是在互连网络的顶点和边上分别部署交换机和双端口服务器,其逻辑图可以抽象为复合图.顶点独立生成树(node-independent spanning trees,NIST)是数据中心网络中的一种重要结构,可用于设计数据中心网络中的可靠通信协议,容错广播和安全消息分发,IP快速重路由等.给定一个复合图G(Kn),首先表明,如果图G的直径为d,则复合图G(Kn)的直径为2d或2d+1.假设n-正则、n-顶点连通的互连网络G中存在以任一顶点为根的n棵NIST,通过提出一种时间复杂度O(N)的高效算法(其中N是顶点数),给出了G(Kn)中一种构造n棵NIST的通用方法.对复合图Qn(Kn)的顶点分析表明,NIST的最大高度仅为其直径加3.另外,基于增广立方体的数据中心网络上的模拟实验也从另一个方面证明了上述结论的正确性.  相似文献   

10.
张修军  吴璞  杨洪  邵泽辉 《计算机科学》2017,44(Z6):129-132
一个无向图G=(V,E)的顶点子集DV是控制集,当且仅当任意一个顶点v∈V-D至少与一个顶点u∈D相邻。图G中的顶点数最少的控制集称为最小控制集,带权控制集问题是求解给定的顶点带权的无向图G的权最小的控制集。结合强弦图的性质,给出基于局部比值法的线性时间算法来求解强弦图带非负权的控制集问题,同时给出了算法复杂度的证明。  相似文献   

11.
设g(x)≤f(x)是定义在V(G)上的两个整数值函数,h(e)∈[0,1]是定义在图G的边集E(G)上的函数。令dGh(x)=移e∈Exh(e),其中Ex={xy:xy∈E(G)}。若对所有的x∈V(G)都有g(x)≤dGh(x)≤f(x)成立,称h是G的一个(g,f)-表示函数。Gh是图G的一个支撑子图使得E(Gh)={e:e∈E(G),h(e)≠0},则称Gh是G的一个分数(g,f)-因子。文章给出,若对V(G)中的任意两个顶点u和v,G-{u,v}有分数k-因子存在。则G有一个分数k-因子不含图G中任意给定的边e∈E(G);当G有分数1-因子F=Gh存在时,对任意e∈F,G-V(e)有分数k-因子存在,则G有分数k-因子。  相似文献   

12.
We provide a new heuristic method approach to search for degree-balanced and small weight routing spanning trees in a network. The method is a modification of Kruskal’s minimum spanning tree search algorithm and is based on a distributed search by hierarchical clusters. It provides spanning trees with a lower maximum weighted degree, a bigger diameter, and can be used for balanced energy consumption routing in wireless sensor networks (WSN’s). The method can be naturally implemented in parallel or as a simple locally distributed algorithm. Simulations for a realistic case scenario WSN are done based on the transmission energy matrix. The simulation results show that the proposed approach can extend the functional lifetime of a WSN in terms of sensor transmission energy by 3–4 times. We also show that the results can be further improved by using a preliminary clustering of the input network.  相似文献   

13.
随着复杂网络研究的兴起,随机图成为一种重要复杂网络模型。基于完全图的生成子图的思想,得到了生成随机图的一种新算法,即用去边的方法生成随机图的算法,并用数值实验验证了加边和去边生成的随机图的统计特性(最大度、最小度、聚集系数、平均最短路径和平均度)是相近的,用去边的方法得到的图的度分布曲线在其平均度处达到峰值,随后呈指数下降,这与随机图的度分布是相同的。为了得到稀疏连通的随机图,又提出了一个不去割边的近似随机图生成算法,并从理论上说明了该算法生成的图是连通的,同时通过数值实验验证了图的连通性,并与加边随机图的统计特性进行了比较。  相似文献   

14.
Given a graph G=(V,E) and two vertices s,t ∈ V , s\neq t , the Menger problem is to find a maximum number of disjoint paths connecting s and t . Depending on whether the input graph is directed or not, and what kind of disjointness criterion is demanded, this general formulation is specialized to the directed or undirected vertex, and the edge or arc disjoint Menger problem, respectively. For planar graphs the edge disjoint Menger problem has been solved to optimality [W2], while the fastest algorithm for the arc disjoint version is Weihe's general maximum flow algorithm for planar networks [W1], which has running time \bf O (|V| log |V|) . Here we present a linear time, i.e., asymptotically optimal, algorithm for the arc disjoint version in planar directed graphs. Received August 1997; revised January 1999.  相似文献   

15.
A Cartesian product network is obtained by applying the cross operation on two graphs. We study the problem of constructing the maximum number of edge-disjoint spanning trees (abbreviated to EDSTs) in Cartesian product networks. Let G=(V/sub G/, E/sub G/) be a graph having n/sub 1/ EDSTs and F=(V/sub F/, E/sub F/) be a graph having n/sub 2/ EDSTs. Two methods are proposed for constructing EDSTs in the Cartesian product of G and F, denoted by G/spl times/F. The graph G has t/sub 1/=|E/sub G/|/spl middot/n/sub 1/(|V/sub G/|-1) more edges than that are necessary for constructing n/sub 1/ EDSTs in it, and the graph F has t2=|E/sub F/'-n/sub 2/(|V/sub F/|-1) more edges than that are necessary for constructing n/sub 2/ EDSTs in it. By assuming that t/sub 1//spl ges/n/sub 1/ and t/sub 2//spl ges/n/sub 2/, our first construction shows that n/sub 1/+n/sub 2/ EDSTS can be constructed in G/spl times/F. Our second construction does not need any assumption and it constructs n/sub 1/+n/sub 2/-1 EDSTs in G/spl times/F. By applying the proposed methods, it is easy to construct the maximum numbers of EDSTs in many important Cartesian product networks, such as hypercubes, tori, generalized hypercubes, mesh connected trees, and hyper Petersen networks.  相似文献   

16.
We present the first polynomial-time approximation scheme (PTAS) for the Minimum Independent Dominating Set problem in graphs of polynomially bounded growth which are used to model wireless communication networks.The approach presented yields a robust algorithm, that is, it accepts any undirected graph as input, and returns a (1+ε)-approximate minimum independent dominating set, or a certificate showing that the input graph does not satisfy the bounded growth property.  相似文献   

17.
Edge coloring, total coloring and L(2,1)-labeling are well-studied NP-hard graph problems. Even the versions asking whether a graph has a coloring with few colors or a labeling with few labels remain NP-hard on graphs of small maximum degree. This paper studies enumeration and counting problems on edge colorings, total colorings and L(2,1)-labelings of graphs. One part deals with the enumeration of all edge 3-colorings, all total 4-colorings and all L(2,1)-labelings of span 5 of a given connected cubic graph. Branching algorithms to solve these enumeration problems are established. They imply upper bounds on the maximum number of edge 3-colorings, total 4-colorings and L(2,1)-labelings of span 5 in any n-vertex connected cubic graphs. Corresponding combinatorial lower bounds are also provided. The other part of the paper studies dynamic programming algorithms solving counting problems. On one hand, algorithms to count the number of edge k-colorings and total k-colorings for graphs of bounded pathwidth are given. On the other hand, an algorithm to count the number of L(2,1)-labelings of span 4 for graphs of maximum degree three are given.  相似文献   

18.
度约束最小生成树问题是网络设计和优化中的一个NP-hard问题。提出一种求解网络G关于指定节点的最大度约束最小生成树的改进算法。算法在保证指定节点最大度的前提下,通过选取剩余边中权最小的边加入当前网络,得到网络G关于指定节点的最大度最小生成树,同时对算法的复杂度进行了分析。最后通过与其他算法的仿真比较,表明新算法的有效性和通用性。  相似文献   

19.
提出了一种基于多生成树和子网-节点度联合权重的静态无线网络极小连通支配集MCDS构造算法SWNMCDS。算法首先设定一个概率p,每个节点随机生成一个概率并与p对比后决定是否成为候选根节点。两跳范围内的候选根节点相互交换信息,确定最终的根节点。每个根节点基于节点权重的连通树生成算法生成多棵连通树。最后基于子网-节点度联合权重选择连通节点,将多棵连通树连成极小连通支配集。经分析,SWNMCDS算法近似比上限为2β(2+H(Δ)),时间复杂度为O(Δ2),消息复杂度为O(Δ2)(Δ为最大一跳邻居节点集合的大小,β为生成树数目)。仿真实验表明,与经典MCDS算法比较,SWNMCDS所构造的连通支配集具有较小的规模。  相似文献   

20.
Given a graph, we define a base set to be a set of integers of size equal to the number of vertices in the graph. Given a graph and a base set, a labeling of the graph from the base set is an assignment of distinct integers from the base set to the vertices of the graph. The gap of an edge in a labeled graph is the absolute value of the difference between the labels of its endpoints. The gap of a labeled graph is the sum of the gaps of its edges.The maximum gap graph labeling problem takes as input a graph and a base set and maximizes the gap of the graph over all possible labelings from the base set. We show that this problem is NP-complete even when the base set is restricted to consecutive integers. We also show that this restricted case has polynomial time approximations that achieve a factor of 2/3 for trees, of 1/2 for bipartite graphs, and of 1/4 for general graphs, with a deterministic algorithm, while an expected factor of 1/3 for general graphs is achieved with a randomized algorithm. The case of general base sets is approximated within an expected factor of 1/16 for general graphs with a randomized polynomial time algorithm. We finally give a polynomial time algorithm that solves the maximum gap graph labeling problem for a graph that has bounded degree and bounded treewidth. The maximum graph labeling problem shows connections with the graceful tree conjecture.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

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