Efficient implementation of graph algorithms using contraction

ABSTRACT

The (component) merging problem is a new graph problem. Versions of this problem appear as bottlenecks in various graph algorithms. A new data structure solves this problem efficiently, and two special cases of the problem have even more efficient solutions based on other data structures. The performance of the data structures is sped up by introducing a new algorithmic tool called packets. The algorithms that use these solutions to the component merging problem also exploit new properties of two existing data structures. Specifically, &Bgr;-trees can be used simultaneously as a priority queue and a concatenable queue. Similarly, F-heaps support some kinds of split operations with no loss of efficiency. An immediate application of the solution to the simplest version of the merging problem is an &Ogr;(t(m, n)) algorithm for finding minimum spanning trees in undirected graphs without using F-heaps, where t(m, n) = mlog2log2logdn, the graph has n vertices and m edges, and d = max(m/n, 2). Packets also improve the F-heap minimum spanning tree algorithm, giving the fastest algorithm currently known for this problem. The efficient solutions to the merging problem and the new observation about F-heaps lead to an &Ogr;(n(t(m, n) + nlogn)) algorithm for finding a maximum weighted matching in general graphs. This settles an open problem posed by Tarjan [ 15, p. 123], where the weaker bound of O(nm log (n2/m)) was conjectured.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: BLUM, M., FLOYD, R., PRATT, V., RIVEST, R., AND TARJAN, R.E. Time bounds for selection. J. Comput. Syst. Sci. 7 (1973), 448-461.
• 3: CHERITON, D., AND TARJAN, R.E. Finding minimum spanning trees. SIAM J. Comput. 5 (1976), 724-741.
• 4: EDMONDS, J. Maximum matching and a polyhedron with 0, 1 vertices. J. Res. NBS 69B (April- June 1965), 125-130.
• 5: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 6: Harold Neil Gabow, Implementation of algorithms for maximum matching on nonbipartite graphs., 1974
• 7: GABOW, H. N. A scaling algorithm for weighted matching on graphs. In Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New .York, 1985, pp. 90-100.
• 8: GABOW, H. N., AND TARJAN, R.E. A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30 (1985), 209-221.
• 9: GABOW, H. N., GALIL, Z., AND SPENCER, T. H. Efficient implementation of graph algorithms using contraction. In Proceedings of the 25th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1984, pp. 347-357.
• 10: H N Gabow , Z Galil , T Spencer , R E Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica, v.6 n.2, p.109-122, 1986 [doi>10.1007/BF02579168]
• 11: Zvi Galil , Silvio Micali , Harold Gabow, An O(EV log V) algorithm for finding a maximal weighted matching in general graphs, SIAM Journal on Computing, v.15 n.1, p.120-130, Feb. 1986 [doi>10.1137/0215009]
• 12: Donald B. Johnson, Efficient Algorithms for Shortest Paths in Sparse Networks, Journal of the ACM (JACM), v.24 n.1, p.1-13, Jan. 1977 [doi>10.1145/321992.321993]
• 13: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 14: LAWLER, E.L. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York, 1976.
• 15: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 16: Jean Vuillemin, A data structure for manipulating priority queues, Communications of the ACM, v.21 n.4, p.309-315, April 1978 [doi>10.1145/359460.359478]
• 17: YAO, A.C. An O(IEI loglog I VI) algorithm for finding minimum spanning trees. Inf. Proc. Lett. 4 (1975), 21-23.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks; Trees

General Terms:
Algorithms, Theory