### Efficient implementation of graph algorithms using contractionEfficient implementation of graph algorithms using contraction

Access Restriction
Subscribed

 Author Gabow, Harold N. ♦ Galil, Zvi ♦ Spencer, Thomas H. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1989 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract The $(\textit{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 $\textit{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 $&Ogr;(\textit{t}(\textit{m},$ $\textit{n}))$ algorithm for finding minimum spanning trees in undirected graphs $\textit{without}$ using F-heaps, where $\textit{t}(\textit{m},$ $\textit{n})$ = $\textit{m}log2log2logd\textit{n},$ the graph has $\textit{n}$ vertices and $\textit{m}$ edges, and $\textit{d}$ = $max(\textit{m}/\textit{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;(\textit{n}(\textit{t}(\textit{m},$ $\textit{n})$ + $\textit{n}log\textit{n}))$ 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 $\textit{O}(\textit{nm}$ log $(\textit{n}2/\textit{m}))$ was conjectured. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1989-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 36 Issue Number 3 Page Count 33 Starting Page 540 Ending Page 572

#### Open content in new tab

Source: ACM Digital Library