Top

previous chapter Pioneering the Establishment of the Foundations...

next chapter Weighted Random Sampling over Data Streams

Hint

Swipe to navigate through the chapters of this book

2015 | OriginalPaper | Chapter

An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs

Read first chapter

Authors: Ka Wong Chong, Christos Zaroliagis

Publisher: Springer International Publishing

Published in: Algorithms, Probability, Networks, and Games

» Get access to the full-text

Abstract

We present an optimal deterministic O(n)-work parallel algorithm for finding a minimum spanning tree on an n-vertex planar graph. The algorithm runs in \(O(\log n)\) time on a CRCW PRAM and in \(O(\log n\log ^*n)\) time on an EREW PRAM. Our results hold for any sparse graph that is closed under taking of minors, as well as for a class of graphs with non-bounded genus.

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

Ahuja, R., Magnanti, T., Orlin, J.: Network Flows. Prentice-Hall, Englewood (1993) MATH

Awerbuch, B., Shiloach, Y.: New connectivity and MSF algorithms for shuffle-exchange network and PRAM. IEEE Trans. Comput. 36(10), 1258–1263 (1987) MathSciNetCrossRefMATH

Bodlaender, H., Hagerup, T.: Parallel algorithms with optimal speedup for bounded treewidth. SIAM J. Comput. 27(6), 1725–1746 (1998) MathSciNetCrossRefMATH

Boruvka, O.: O jistém problému minimálním. Práca Moravské Přírodovědecké Společnosti 3, 37–58 (1926)

Chazelle, B.: A minimum spanning tree algorithm with inverse-Ackermann type complexity. J. ACM 47(6), 1028–1047 (2000) MathSciNetCrossRefMATH

Cheriton, D., Tarjan, R.E.: Finding minimum spanning trees. SIAM J. Comput. 5, 724–742 (1976) MathSciNetCrossRefMATH

Chin, F.Y., Lam, J., Chen, I.N.: Efficient parallel algorithms for some graph problems. Commun. ACM 25(9), 659–665 (1982) MathSciNetCrossRefMATH

Chong, K.W.: Finding minimum spanning trees on the EREW PRAM. In: Proceedings of the International Computer Symposium—ICS’96, pp. 7–14. Taiwan (1996)

Chong, K.W., Lam, T.W.: Finding connected components in \(O(\log n\log \log n)\) time on the EREW PRAM. J. Algorithms 18, 378–402 (1995) MathSciNetCrossRefMATH

10.

Chong, K.W., He, Y., Lam, T.W.: Concurrent threads and optimal parallel minimum spanning trees algorithm. J. ACM 48(2), 297–323 (2001) MathSciNetCrossRefMATH

11.

Cole, R., Klein, P.N., Tarjan, R.E.: Finding minimum spanning forests in logarithmic time and linear work using random sampling. In: Proceedings of the 8th ACM symposium on Parallel Algorithms and Architectures (ACM), pp. 243–250 (1996)

12.

Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control 70, 32–53 (1986) MathSciNetCrossRefMATH

13.

Cole, R., Vishkin, U.: Approximate and exact parallel scheduling with applications to list, tree and graph problems. In: Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, pp. 478–491. IEEE (1986)

14.

Fredman, M., Willard, D.E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci. 48, 533–551 (1994) MathSciNetCrossRefMATH

15.

Gabow, H., Galil, Z., Spencer, T., Tarjan, R.E.: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6(2), 109–122 (1986) MathSciNetCrossRefMATH

16.

Goldberg, A., Plotkin, S., Shannon, G.: Parallel symmetry-breaking in sparse graphs. SIAM J. Discrete Math. 1, 434–446 (1988) MathSciNetCrossRefMATH

17.

Hagerup, T.: Optimal parallel algorithms on planar graphs. Inf. Comput. 84, 71–96 (1990) MathSciNetCrossRefMATH

18.

Hagerup, T.: Optimal Parallel Computation of Minimum Spanning Forests in Planar Graphs, Technical Report 11/1990. Universität des Saarlandes, May 1990

19.

Hagerup, T., Chrobak, M., Diks, K.: Optimal parallel 5-colouring of planar graphs. SIAM J. Comput. 18(2), 288–300 (1989) MathSciNetCrossRefMATH

20.

Harary, F.: Graph Theory. Addison-Wesley, Reading (1969) MATH

21.

JáJá, J.: An Introduction to Parallel Algorithms. Addison-Wesley, Reding (1992) MATH

22.

Johnson, D.B., Metaxas, P.: Connected components in \(O(\log ^{3/2}|V|)\) parallel time for the CREW PRAM. In: Proceeings of 32nd IEEE Symposium on Foundations of Computer Science, pp. 688–695, IEEE (1991)

23.

Johnson, D.B., Metaxas, P.: A parallel algorithm for computing minimum spanning trees. J. Algorithms 19, 383–401 (1995) MathSciNetCrossRefMATH

24.

Karger, D.R.: Approximating, verifying, and constructing minimum spanning trees. Unpublished manuscript (1992)

25.

Karger, D.R., Klein, P.N., Tarjan, R.E.: A randomized linear-time algorithm to find minimum spanning trees. J. ACM 42(2), 321–328 (1995) MathSciNetCrossRefMATH

26.

Karp, R., Ramachandran, V.: Parallel Algorithms for Shared-Memory Machines. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, vol. A, pp. 869–941. Elsevier, Amsterdam (1990)

27.

Pettie, S., Ramachandran, V.: An optimal minimum spanning tree algorithm. J. ACM 49(1), 16–34 (2002) MathSciNetCrossRefMATH

28.

Pettie, S., Ramachandran, V.: A randomized time-work optimal parallel algorithm for finding a minimum spanning forest. SIAM J. Comput. 31(6), 1879–1895 (2002) MathSciNetCrossRefMATH

29.

Zaroliagis, C.D.: Simple and work-efficient parallel algorithms for the minimum spanning tree problem. Parallel Process. Lett. 7(1), 25–37 (1997) MathSciNetCrossRef

Title

An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs

Book

Algorithms, Probability, Networks, and Games

Print ISBN: 978-3-319-24023-7

Electronic ISBN: 978-3-319-24024-4

https://doi.org/10.1007/978-3-319-24024-4

DOI

https://doi.org/10.1007/978-3-319-24024-4_11

Authors:

Ka Wong Chong
Christos Zaroliagis

Publisher

Springer International Publishing

Sequence number

Premium Partner

Image Credits