Harold N. Gabow
Zvi Galil
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, Β-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 Ο(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 Ο(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.
- 1 AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J. D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974. Google Scholar
- 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.Google Scholar
- 3 CHERITON, D., AND TARJAN, R.E. Finding minimum spanning trees. SIAM J. Comput. 5 (1976), 724-741.Google Scholar
- 4 EDMONDS, J. Maximum matching and a polyhedron with 0, 1 vertices. J. Res. NBS 69B (April- June 1965), 125-130.Google Scholar
- 5 FREDMAN, M. L., AND TARJAN, R. E. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34, 3 (July 1987), 596-615. Google Scholar
- 6 GABOW, H.N. Implementation of algorithms for maximum matching on nonbipartite graphs. Ph.D. Dissertation. Dept. of Comput. Sci., Stanford Univ., Stanford, Calif., 1973. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 10 GABOW, H. N., GALIL, Z., SPENCER, T. H., AND TARJAN, R.E. Efficient algorithms for minimum spanning trees on directed and undirected graphs. Combinatorica 6 (1886), 109-122. Google Scholar
- 11 GALIL, Z., MICALI, S., AND GABOW, H. Priority queues with variable priority and an O(EVlog V) algorithm for finding a maximal weighted matching in general graphs. SIAM J. Com.put. 15 (1986), 120-150. Google Scholar
- 12 JOHNSON, D.B. Efficient algorithms for shortest paths in sparse networks. J. ACM 24, 1 (Jan. 1977), 1-13. Google Scholar
- 13 KNUTH, D. E. The Art of Computer Programming. Vol. 3: Sorting and Searching. Addison- Wesley, Reading, Mass., 1973. Google Scholar
- 14 LAWLER, E.L. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York, 1976.Google Scholar
- 15 TARJAN, R.E. Data Structures and Network Algorithms. SIAM Publication, Philadelphia, Pa., 1983. Google Scholar
- 16 VUILLEMIN, J. A data structure for manipulating priority queues. Commun. ACM 21, 4 (Apr. 1978), 309-314. Google Scholar
- 17 YAO, A.C. An O(IEI loglog I VI) algorithm for finding minimum spanning trees. Inf. Proc. Lett. 4 (1975), 21-23.Google Scholar
Index Terms
- Efficient implementation of graph algorithms using contraction
Recommendations
Trivially noncontractible edges in a contraction critically 5-connected graph
An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. A k-connected graph with no k-contractible edge is said to be contraction critically k-connected. An edge of a k-connected graph ...
The number of vertices of degree 7 in a contraction-critical 7-connected graph
An edge of a k-connected graph is said to be k-contractible if its contraction yields a k-connected graph. A non-complete k-connected graph possessing no k-contractible edges is called contraction-critical k-connected. Let G be a contraction-critical 7-...
The number of vertices of degree 5 in a contraction-critically 5-connected graph
An edge of a 5-connected graph is said to be 5-contractible if the contraction of the edge results in a 5-connected graph. A 5-connected graph with no 5-contractible edge is said to be contraction-critically 5-connected. Let V(G) and V"5(G) denote the ...
Reviews
S. Srinivasan
The authors study an efficient implementation of graph algorithms. Their main contribution is in the area of merging components. The authors introduce the notion of packets, which means a certain number of edges are grouped into a packet. The advantage is that when an algorithm requires multiple phases, we only need to look at the packet minima. This approach enables the authors to obtain a more efficient (timewise) algorithm for finding minimum spanning trees in undirected graphs without using F-heaps. This result improves the work of Fredman and Tarjan [1], which uses F-heaps. This paper also addresses the reverse problem of merging, namely splitting. The authors suggest two different approaches to support the usual operations such as initialize, insert, delete, find, and split. This part requires the concept of &bgr;-trees, which are B-trees of order &bgr;. The paper concludes with six open questions. Even though several definitions are needed in a paper of this type, the authors have kept the paper very much self-contained. Several related works are identified in the references. The proofs are easy to follow. This paper makes an important contribution to the merging/splitting problem and will be of interest primarily for researchers in this area.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments