首页 | 本学科首页   官方微博 | 高级检索  
     


Algorithms for dense graphs and networks on the random access computer
Authors:J Cheriyan  K Mehlhorn
Affiliation:(1) Department of Combinatorics and Optimization, University of Waterloo, N2L 3G1 Waterloo, Ontario, Canada;(2) Max-Planck-Institut für Informatik and Universität des Saarlandes, D-66123 Saarbrücken, Germany
Abstract:We improve upon the running time of several graph and network algorithms when applied to dense graphs. In particular, we show how to compute on a machine with word size lambda=OHgr (logn) a maximal matching in ann-vertex bipartite graph in timeO(n 2+n 2.5/lambda)=O(n 2.5/logn), how to compute the transitive closure of a digraph withn vertices andm edges in timeO(n 2+nm/lambda), how to solve the uncapacitated transportation problem with integer costs in the range O.C] and integer demands in the range –U.U] in timeO ((n 3 (log log/logn)1/2+n2 logU) lognC), and how to solve the assignment problem with integer costs in the range O.C] in timeO(n 2.5 lognC/(logn/loglogn)1/4).Assuming a suitably compressed input, we also show how to do depth-first and breadth-first search and how to compute strongly connected components and biconnected components in timeO(nlambda+n 2/lambda), and how to solve the single source shortest-path problem with integer costs in the range O.C] in time0 (n 2(logC)/logn). For the transitive closure algorithm we also report on the experiences with an implementation.Most of this research was carried out while both authors worked at the Fachbereich Informatik, Universität des Saarlandes, Saarbrücken, Germany. The research was supported in part by ESPRIT Project No. 3075 ALCOM. The first author acknowledges support also from NSERC Grant No. OGPIN007.
Keywords:Graph  Network  Algorithm  Dense graph  Dense network
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号