ISSN:
1432-0541
Keywords:
Graph
;
Network
;
Algorithm
;
Dense graph
;
Dense network
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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 λ=Ω (logn) a maximal matching in ann-vertex bipartite graph in timeO(n 2+n 2.5/λ)=O(n 2.5/logn), how to compute the transitive closure of a digraph withn vertices andm edges in timeO(n 2+nm/λ), 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(nλ+n 2/λ), 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01940880
Permalink
