【摘 要】
：
给定一个有向图,一个k步可达查询u→?kv用来回答在该图中是否存在一条从顶点u到顶点v且长度不大于k的有向路径。k步可达查询是一种基本的图操作并在过去十年间被广泛地研究。
【基金项目】
：
国家重点研发计划(2017YFB0309800)
论文部分内容阅读
给定一个有向图,一个k步可达查询u→?kv用来回答在该图中是否存在一条从顶点u到顶点v且长度不大于k的有向路径。k步可达查询是一种基本的图操作并在过去十年间被广泛地研究。已有的k步可达查询算法仍存在许多弊端,例如不可达查询效率低,索引规模大和索引构建时间长等。本文针对上述问题提出了2种优化方法,分别是基于互逆拓扑序号以及基于等价顶点的图压缩方法.前者提高了不可达查询的效率,后者减少了索引规模和索引构建时间。实验结果表明,本文提出的方法可以有效地处理k步可达查询,并支持大规模数据的处理。
其他文献
习近平总书记高度重视学校人才培养工作,立足新时代“两大格局”,从建设社会主义现代化强国实现中华民族伟大复兴的时代使命出发,将劳动教育纳入人才培养目标,丰富发展了党的
湿式静电除尘器依靠水膜冲刷进行清灰,实际工作中气流温度对水膜蒸发速率、伏安特性及除尘效率具有一定影响。本文将碳纤维布、PVC刻槽板分别作为湿式静电除尘器的收尘极,用
随着现代物流的发展,传统的仓储系统由于效率低下已不能满足行业的发展需要。本文提出一种集成现代新科技的自动化立体仓储系统的解决方案,并设计了其机电传动与控制系统。该
浅埋偏压小净距隧道结构特殊,两主洞同时施工时掌子面间距的合理选择对隧道稳定性尤为重要。以延崇高速公路头炮隧道为背景,通过ANSYS及FLAC3D软件建立隧道模型并进行数值模
随着我国各项信息技术发展的不断推进,在人们生活中的很多领域都应用了可编程控制技术,PLC 自动控制系统为其 操作的可行性提供了必要的保障,这种优越性同时的体现与于便捷的
针对传统边坡位移量预测参数的局限和不足,以及在小样本下的预测参数估计区间较宽会导致工程设计偏于保守的问题,以垂直位移方向率作为边坡稳定性演化分析与评价的一个有效位
随着“公共植保,绿色植保”理念的落实,我国农业产品的质量和安全问题逐渐得到社会各界的广泛关注。采取切实 有效的措施对农作物病虫害实施集中化、专业化的防治,是缓解劳动
机器阅读理解任务是衡量模型对于文本信息理解程度的一种重要方式,一直以来备受关注。近年来,很多学者在这一任务上提出了自己的模型,并取得了相当不错的成绩,其中一部分甚至
在信息技术不断进步和推广应用的背景下,由于具备独特的技术优势,所以为人们的生产生活提供了很多的便利,通 过将其运用到幼儿教育教学活动中,将会产生非常重要的影响,这是现
油田在我国经济发展中具有重要作用,其产品具有一定特殊性,在具体生产中需秉承正确的理念,深刻贯彻落实习近平总书记“当好标杆旗帜、建设百年油田”的指导方针,以打造政治素