期刊文献+
共找到27篇文章
< 1 2 >
每页显示 20 50 100
Depth First:Optimal Path Discovery Between Designated Nodes in Random Ring-Based Graphs
1
作者 Li Qi Xu Jiasheng +4 位作者 Zhang Haonan Kang Huquan Fu Luoyi Long Fei Wang Xinbing 《China Communications》 SCIE CSCD 2024年第9期225-241,共17页
This paper focuses on optimally determining the existence of connected paths between some given nodes in random ring-based graphs.Serving as a fundamental underlying structure in network modeling,ring topology appears... This paper focuses on optimally determining the existence of connected paths between some given nodes in random ring-based graphs.Serving as a fundamental underlying structure in network modeling,ring topology appears as commonplace in many realistic scenarios.Regarding this,we consider graphs composed of rings,with some possible connected paths between them.Without prior knowledge of the exact node permutations on rings,the existence of each edge can be unraveled through edge testing at a unit cost in one step.The problem examined is that of determining whether the given nodes are connected by a path or separated by a cut,with the minimum expected costs involved.Dividing the problem into different cases based on different topologies of the ring-based networks,we propose the corresponding policies that aim to quickly seek the paths between nodes.A common feature shared by all those policies is that we stick to going in the same direction during edge searching,with edge testing in each step only involving the test between the source and the node that has been tested most.The simple searching rule,interestingly,can be interpreted as a delightful property stemming from the neat structure of ring-based networks,which makes the searching process not rely on any sophisticated behaviors.We prove the optimality of the proposed policies by calculating the expected cost incurred and making a comparison with the other class of strategies.The effectiveness of the proposed policies is also verified through extensive simulations,from which we even disclose three extra intriguing findings:i)in a onering network,the cost will grow drastically with the number of designated nodes when the number is small and will grow slightly when that number is large;ii)in ring-based network,Depth First is optimal in detecting the connectivity between designated nodes;iii)the problem of multi-ring networks shares large similarity with that of two-ring networks,and a larger number of ties between rings will not influence the expected cost. 展开更多
关键词 connectivity analysis cost minimization path discover ring-based graph
下载PDF
Manhattan空间有障碍的最短路径和3-Steiner树算法 被引量:4
2
作者 周智 蒋承东 +1 位作者 黄刘生 顾钧 《软件学报》 EI CSCD 北大核心 2003年第9期1503-1514,共12页
在VLSI设计中,多点互连是物理设计阶段的关键问题之一,而互连的点数等于2或大于2分别对应于Manhattan空间上有障碍时的最短路径问题和最小Steiner树问题,显然前者是后者的基础.连接图是研究最短路径问题的有效工具,已有的典型连接图包... 在VLSI设计中,多点互连是物理设计阶段的关键问题之一,而互连的点数等于2或大于2分别对应于Manhattan空间上有障碍时的最短路径问题和最小Steiner树问题,显然前者是后者的基础.连接图是研究最短路径问题的有效工具,已有的典型连接图包括基于轨迹的GC和GT以及基于自由区的GF和GG.工作包括3个方面:设计并分析了在各种连接图上实现动态的点对之间的最短路径查询算法;分析了在各个连接图上构造3-Steiner树的算法,对于已有的GC上的3-Steiner算法,将其Steiner顶点的候选集合规模从O((e+p)2)降低到了O((t+p)2),其中e,t,p分别表示边数、障碍极边数和顶点数;设计了在GG上的3-Steiner树构造算法,其平均情况时间复杂度只有Q(t). 展开更多
关键词 VLSI设计 连接图 最短路径 最小Steiner树
下载PDF
一种新的基于ISOMAP的数据可视化算法 被引量:3
3
作者 邵超 黄厚宽 《计算机研究与发展》 EI CSCD 北大核心 2007年第7期1137-1143,共7页
作为古典MDS算法的一个非线性扩展,ISOMAP算法能较好地对嵌入在高维欧氏空间中的低维非线性流形进行可视化.然而,ISOMAP算法不但要求数据具有良好抽样且位于单一流形之上,而且还依赖于难以有效选取的邻域大小,这极大地限制了该算法的实... 作为古典MDS算法的一个非线性扩展,ISOMAP算法能较好地对嵌入在高维欧氏空间中的低维非线性流形进行可视化.然而,ISOMAP算法不但要求数据具有良好抽样且位于单一流形之上,而且还依赖于难以有效选取的邻域大小,这极大地限制了该算法的实际应用.为此提出了一种改进算法——GISOMAP,它采用MDS算法的一个变种来减弱长测地距离和"短路"边对距离保持的影响,不但能更好地对具有多聚类结构的数据进行可视化,而且对邻域大小也不再敏感,从而能更容易地得到实际应用. 展开更多
关键词 数据可视化 ISOMAP GISOMAP 最小连通邻域图 成本
下载PDF
基于最小连通邻域图的ISOMAP算法 被引量:2
4
作者 邵超 万春红 陈广宇 《计算机应用》 CSCD 北大核心 2007年第10期2570-2574,共5页
噪音的干扰和邻域大小的不合适会在ISOMAP算法的邻域图中引入"短路"边,使其不能正确表达数据的邻域结构,从而使该算法具有较差的鲁棒性和拓扑稳定性。为此,根据最小连通邻域图能有效避免"短路"边的特点,提出了一种... 噪音的干扰和邻域大小的不合适会在ISOMAP算法的邻域图中引入"短路"边,使其不能正确表达数据的邻域结构,从而使该算法具有较差的鲁棒性和拓扑稳定性。为此,根据最小连通邻域图能有效避免"短路"边的特点,提出了一种能有效删除"短路"边因而更具鲁棒性和拓扑稳定性的ISOMAP算法——基于最小连通邻域图的ISOMAP(MCNG-ISOMAP)算法。该算法能在一定程度上避免邻域大小难以有效选取的问题,同时还能在不依赖于邻域大小的情况下发现数据真正的固有维数。 展开更多
关键词 等距映射 MCNG-ISOMAP 最小连通邻域图 成本 “短路”边
下载PDF
恰含5条非基本边的极小3连通图 被引量:1
5
作者 陈仪朝 苏健基 《广西师范大学学报(自然科学版)》 CAS 2004年第3期29-34,共6页
简单极小 3连通图 G中的一条不在任何三边形中的边 e收缩之后所得到的图如果仍 3连通 ,则称 e为 G的非基本边 .Oxley与 Wu证明不是轮的简单极小 3连通图至少包含 3条非基本边 ,并且刻画了恰含 3条或 4条非基本边的不是轮的简单极小 3连... 简单极小 3连通图 G中的一条不在任何三边形中的边 e收缩之后所得到的图如果仍 3连通 ,则称 e为 G的非基本边 .Oxley与 Wu证明不是轮的简单极小 3连通图至少包含 3条非基本边 ,并且刻画了恰含 3条或 4条非基本边的不是轮的简单极小 3连通图 .现刻画恰含 5条非基本边的不是轮的简单极小 3连通图 ,它们是 1 展开更多
关键词 图论 极小3连通图 可收缩边 非基本边
下载PDF
非线性流水线优化中MAL的一种计算方法 被引量:1
6
作者 曾仁京 《微电子学与计算机》 CSCD 北大核心 2003年第3期58-60,76,共4页
文章介绍一种将含多环有向多重连通图分解为顶点带环且彼此孤立的有向简单图G1和顶点无环的有向多重连通图G2的方法,并在G2上用启发式搜索算法求非线性流水线的最小平均等待时间MAL。
关键词 非线性流水线 优化 MAL 计算方法 启发式搜索 最小连通图 有向多重图 算法
下载PDF
一类几乎可约矩阵的本原指数 被引量:3
7
作者 李毓祁 《海南大学学报(自然科学版)》 CAS 2004年第1期15-22,共8页
应用图论方法推导出至少有一对非零对称元但非对称的n阶本原几乎可约矩阵所成的类(SNBn)的数个指数公式,并进一步确定出(SNBn)的本原指数集(S1∪S2∪S3).
关键词 几乎可约矩阵 本原指数 本原矩阵 极小强连通有向图 布尔矩阵
下载PDF
最小支撑树的新算法 被引量:1
8
作者 连海峰 雷雪萍 《淮阴师范学院学报(自然科学版)》 CAS 2004年第1期11-13,共3页
从树的等价定义出发,叙述并证明了一种不必考虑圈的求最小支撑树的算法.
关键词 连通赋权简单图 支撑树 最小支撑树
下载PDF
普里姆(Prim)算法另解 被引量:1
9
作者 刘平原 张霓 《科学中国人》 2007年第7期125-126,共2页
在《数据结构》有关图的章节中,对最小生成树两大算法的解释都是基于MST性质来说明的。由于MST性质每次是选取原图集中值最小两栖边来构造最小生成树,这个过程较为复杂,现可以反其道而行之,采用“破圈法”——每次删除权值最大的边,来... 在《数据结构》有关图的章节中,对最小生成树两大算法的解释都是基于MST性质来说明的。由于MST性质每次是选取原图集中值最小两栖边来构造最小生成树,这个过程较为复杂,现可以反其道而行之,采用“破圈法”——每次删除权值最大的边,来产生最小生成树,过程简洁、结果相同,同时可以证明其正确性,不失为一好算法。 展开更多
关键词 无向连通图 有向连通图 连通子 生成树 最小生成树 MST性质 最小两栖边 普里姆算法 破圈法
下载PDF
无向加权图的K点连通扩充算法
10
作者 孙雨耕 贺昌科 杨山 《电子学报》 EI CAS CSCD 北大核心 1992年第11期101-103,共3页
本文首先研究了无权情况下的极小K点连通扩充算法;然后成功地将模拟退火方法应用于任意无向加权图的K点连通扩充问题,提出了一个O(ΩK|V|~4)的近似算法,为解决加权图的扩充问题提供了一种新途径.
关键词 无向加权图 K点连通 扩充 算法
下载PDF
极小k边连通有向图中出度为k的点(英文)
11
作者 袁旭东 李敏 《广西师范大学学报(自然科学版)》 CAS 2004年第2期25-31,共7页
设k是正整数,D是极小k边连通简单有向图.Mader猜测(见Combinatorics,PaulErdo¨sisEighty(Vol.2),Budapest,1996)D中至少有k+1个出度为k的点.在k=1时,Mader已证明成立.考虑k≥2,运用Edmonds等人在研究组合优化问题中引入的对无交叉... 设k是正整数,D是极小k边连通简单有向图.Mader猜测(见Combinatorics,PaulErdo¨sisEighty(Vol.2),Budapest,1996)D中至少有k+1个出度为k的点.在k=1时,Mader已证明成立.考虑k≥2,运用Edmonds等人在研究组合优化问题中引入的对无交叉组的树表示,证明了在k≥2时,D中至少有3个出度为k的点. 展开更多
关键词 极小k边 连通有向图 出度 无交叉组
下载PDF
简单图含有完全子图的一个充分条件
12
作者 王斌 李霄民 《重庆工商大学学报(自然科学版)》 2005年第1期8-9,共2页
从生活中的一个问题出发,运用图论知识进行了分析,得到了结论,并且对结论进行了推广 得到了在一般情况下简单图含有完全子图的充分条件 并且,在度数要求方面。
关键词 完全子图 简单图 充分条件 图论 结论 推广 一般 要求 知识 度数
下载PDF
极小n棱连通图的着色与棱数
13
作者 郭知熠 《华中理工大学学报》 CSCD 北大核心 1989年第4期133-136,共4页
Mader证明极小n连通图是n+1色可着的,本文证明极小n棱连通图也是n+1色可着的。并且对极小n棱连通图的棱数界进行了估计,证明了若G是p阶极小n棱连通图,则G的棱数e(G)≤n(p-1)。
关键词 极小n棱 连通图 棱连通度 色数
下载PDF
极小k-连通图中的k-可收缩边
14
作者 齐恩凤 王美艳 《菏泽学院学报》 2008年第2期18-20,36,共4页
Ando证明了如果G是极小的k-连通图,且G中不含有K1+C4,若对于V(G)中的任意一个k度点x,与x关联的边中都存在一条不在三边形中的边,那么G中含有k-可收缩边.改进这个结果得出结论:如果G是极小的k-连通图,且不含图P,若G中任一k度点x,都存在与... Ando证明了如果G是极小的k-连通图,且G中不含有K1+C4,若对于V(G)中的任意一个k度点x,与x关联的边中都存在一条不在三边形中的边,那么G中含有k-可收缩边.改进这个结果得出结论:如果G是极小的k-连通图,且不含图P,若G中任一k度点x,都存在与x关联的不在三边形中的边,那么G中有k-可收缩边. 展开更多
关键词 极小k-连通图 k-可收缩边 H—free
下载PDF
求解圆盘图中最小连通支配集的近似算法
15
作者 赵学锋 《计算机应用》 CSCD 北大核心 2011年第7期1962-1965,共4页
针对无线传感器网络常用的拓扑模型单位圆盘图,提出了基于分布式贪心策略的近似算法DDT,在算法执行的每一轮中,根据一跳邻域范围内的权值和邻居的状态信息,选举出节点并和已确定的节点连接,逐步构造出网络图中的一个支配树。用概率方法... 针对无线传感器网络常用的拓扑模型单位圆盘图,提出了基于分布式贪心策略的近似算法DDT,在算法执行的每一轮中,根据一跳邻域范围内的权值和邻居的状态信息,选举出节点并和已确定的节点连接,逐步构造出网络图中的一个支配树。用概率方法研究了支配树中的节点度的性质,通过对极大独立集和最小连通支配集之间关系的分析,得到单位圆盘图中最小连通支配集问题一个新的近似比。计算结果表明,和相关的分布式算法相比,DDT产生的连通支配集在规模上更优。 展开更多
关键词 最小连通支配集 极大独立集 近似算法 支配树 单位圆盘图
下载PDF
极小n-棱连通图的一个定理
16
作者 郭知熠 《土木工程与管理学报》 1989年第3期61-64,共4页
本文讨论极小n-棱连通图的最小度点数。证明了:一个极小n-棱连通图至少有△(G)个度为n的点,其中△(G)指G中的最大度数。推广了文[1][2]的定理。
关键词 极小n-棱连通图 最小度点数 定理
下载PDF
k-点连通图连通度的不变性
17
作者 刘林忠 车琦生 张忠辅 《兰州铁道学院学报》 1998年第2期71-71,共1页
在Thomassen定理[1]的基础上,推广了Thomassen定理的结果并讨论了收缩边,加边和去边之后图的点连通度的不变性及该边应具有的性质.
关键词 点连通度 极点点连通图 点截集
下载PDF
不含禁用子图的极小κ-连通图
18
作者 齐恩凤 《洛阳师范学院学报》 2007年第5期25-27,共3页
本文得到:如果G是极小的κ-连通图,且不合图F,若对于G中任一κ度点力,都存在与力关联的不在三边形中的边,那么G中有κ-可收缩边。
关键词 k-可收缩边 极小k-连通图
下载PDF
极小拟(k+1)连通图的最小度 被引量:2
19
作者 蒋红星 苏健基 《数学研究》 CSCD 2002年第2期187-193,共7页
给出了极小拟 5连通图及围长大于或者等于 4的极小拟 (k+ 1)
关键词 连通图 拟(k +1)连通图 极小拟(k+1)连通图
下载PDF
判定k-点连通图与k-边连通图极小性的定理 被引量:2
20
作者 谢果 《四川师范大学学报(自然科学版)》 CAS CSCD 2000年第5期489-490,共2页
主要研究了判定k 点连通图是极小的充要条件和k 边连通图是极小的必要条件 .
关键词 极小k-点连通图 极小k-边连通图 极小性 判定
下载PDF
上一页 1 2 下一页 到第
使用帮助 返回顶部