Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
A Glimpse at Paul G. Spirakis Read chapter Read first chapter

2015 | OriginalPaper | Chapter

An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs

Authors : Ka Wong Chong, Christos Zaroliagis

Published in: Algorithms, Probability, Networks, and Games

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

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




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

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




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Pioneering the Establishment of the Foundations of the Internet of Things
next chapter Weighted Random Sampling over Data Streams
Literature
1.
Ahuja, R., Magnanti, T., Orlin, J.: Network Flows. Prentice-Hall, Englewood (1993)MATH
2.
Awerbuch, B., Shiloach, Y.: New connectivity and MSF algorithms for shuffle-exchange network and PRAM. IEEE Trans. Comput. 36(10), 1258–1263 (1987)MathSciNetCrossRefMATH
3.
Bodlaender, H., Hagerup, T.: Parallel algorithms with optimal speedup for bounded treewidth. SIAM J. Comput. 27(6), 1725–1746 (1998)MathSciNetCrossRefMATH
4.
Boruvka, O.: O jistém problému minimálním. Práca Moravské Přírodovědecké Společnosti 3, 37–58 (1926)
5.
6.
7.
8.
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)
9.
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.
17.
18.
Hagerup, T.: Optimal Parallel Computation of Minimum Spanning Forests in Planar Graphs, Technical Report 11/1990. Universität des Saarlandes, May 1990
19.
20.
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.
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.
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
Metadata
Title
An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs
Authors
Ka Wong Chong
Christos Zaroliagis
Copyright Year
2015
Book
Algorithms, Probability, Networks, and Games

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

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

Copyright Year: 2015

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

Premium Partner

    Image Credits