Average-case complexity of shortest-paths problems [Elektronische Ressource] / Volker Priebe

Average-case complexity of shortest-paths problemsVolker PriebeDissertationzur Erlangung des GradesDoktor der Ingenieurwissenschaften (Dr.-Ing.)der Naturwissenschaftlich-Technischen Fakult at Ider Universit at des SaarlandesSaarbruc ken2001Tag des Kolloquiums: 1. Juni 2001Dekan: Prof. Dr. Rainer Schulze-Pillot-ZiemenGutachter: Prof. Dr. Kurt MehlhornProf. Alan Frieze, Ph. D.iiAbstract. We study both upper and lower bounds on the average-case complexity of shortest-paths algorithms. It is proved that the all-pairs shortest-paths problem on n-vertex networks can2be solved in time O(n logn) with high probability with respect to various probability distributionson the set of inputs. Our results include the rst theoretical analysis of the average behaviorof shortest-paths algorithms with respect to the vertex-potential model, a family of probabilitydistributions on complete networks with arbitrary real arc costs but without negative cycles. Wealso generalize earlier work with respect to the common uniform model, and we correct the analysisof an algorithm with respect to the endpoint-independent model. For the algorithm that solves theall-pairs shortest-paths problem on networks generated according to the vertex-potential model, akey ingredient is an algorithm that solves the single-source shortest-paths problem on such networks2in time O(n ) with high probability.