A shortest cycle for each vertex of a graph

作     者：Yuster, Raphael 

作者机构：Univ Haifa Dept Math IL-31905 Haifa Israel 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2011年第111卷第21-22期

页      面：1057-1061页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Graph algorithms Girth Shortest path Undirected graph 

摘      要：We present an algorithm that finds, for each vertex of an undirected graph, a shortest cycle containing it. While for directed graphs this problem reduces to the All-Pairs Shortest Paths problem, this is not known to be the case for undirected graphs. We present a truly sub-cubic randomized algorithm for the undirected case. Given an undirected graph with n vertices and integer weights in 1,...,M, it runs in (O) over tilde(root Mn(omega+3)/2) time where omega (Mn(omega)t) time. For the case of bounded real edge weights, a variant of our algorithm solves the problem up to an additive error of epsilon in (O) over tilde (n((omega+6)/3)) time. (C) 2011 Elsevier B.V. All rights reserved.