含有两个非临界点的强连通定向图的弧数(英文)

证明顶点数为n≥4，弧数为m≥（n-1/）＋3的强连通定向图D中存在两点u^＊、u^＊，使得D—u^＊和D-^＊都是强连通的，并用例子说明这里所给的关于弧数的下界是紧的．

基于强连通分量的个性化的网页排名高效算法

个性化的网页排名(PPR)是一种常用的图结点排名方法.随着图的规模变得越来越大,如何快速地计算出PPR逐渐成为大家研究的关注热点.该文的最终目的即是为了提高PPR的计算效率.现有的各种优化算法可大体分为分布式算法和串行算法,其主要思路均是通过将大图上的计算分割到多个小子图上进行计算,但不同分块间的数据通信量往往很大而且通信次数频繁.该文提出的基于强连通分量的算法可有效解决此类问题.其主要计算过程为,首先快速将大量与计算无关的结点和边剪切掉,其次通过某种策略将在大图上的计算转化到多个强连通分量子图上计算,使得各分量子图之间的数据传递只需一次即可完成.该文基于强连通分量算法,不仅减少了分布式算法子图间的通信量,而且降低了串行算法的磁盘读写I/O频率,同时还保证了算法的准确度几乎不受损失.实验结果表明该文提出的算法可显著提高PPR的计算效率.

有向网络中强连通支撑子图扩容问题

针对有向网络中的强连通支撑子图弧扩容问题,提出了 GSCSCE模型.首先研究不受限制的两种特殊情况:最少弧强连通支撑子图扩容问题(MNSCSCE)和最小费用强连通支撑子图扩容问题(MCSCSCE),并把它们的模型转化为赋权形式的强连通支撑子图问题,分别给出了 2-近似算法,时间复杂性均为O(mn).最后讨论受限制问题的特殊情况:最少弧受限强连通支撑子图扩容问题(NCSCSS),用支撑树形图的简单变换给出了一个2-近似算法,时间复杂性为O(mn).

基于逾渗理论的交通路网通行效率分析

针对城市路网的拥堵现象,利用逾渗理论对路网模型的通行效率进行分析。首先,利用实际城市道路的地理数据,应用原始法来构建交通路网模型;然后,对路网通行效率进行量化计算,分析在不同天气状况下拥堵路段对交通态势的影响。文中主要通过路网规则的制定、阈值的分析、强连通子图的划分和通行效率的计算来实现对交通态势的评估,并在不同的天气状况下验证天气因素对交通路网的影响。