Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Theory of Computing Systems
Erschienen in: Theory of Computing Systems 4/2017

20.09.2016

Optimal Decremental Connectivity in Planar Graphs

verfasst von: Jakub Łącki, Piotr Sankowski

Erschienen in: Theory of Computing Systems | Ausgabe 4/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We show an algorithm for dynamic maintenance of connectivity information in an undirected planar graph subject to edge deletions. Our algorithm may answer connectivity queries of the form “Are vertices u and v connected with a path?" in constant time. The queries can be intermixed with any sequence of edge deletions, and the algorithm handles all updates in a total of O(n) time. This results improves over a previously known O(n log n) time algorithm.
Vorheriger Artikel New Pairwise Spanners
Nächster Artikel Dynamic Planar Embeddings of Dynamic Graphs

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Fußnoten
1
Throughout the paper we use n and m to denote, respectively, the number of vertices and the number of edges in the graph.
 
2
Since the graph has constant degree, we may assure that both searches are synchronized in terms of number of vertices visited.
 
Literatur
1.
Alstrup, S., Secher, J.P., Spork, M.: Optimal on-line decremental connectivity in trees. Inf. Process. Lett. 64(4), 161–164 (1997)MathSciNetCrossRefMATH
2.
Eppstein, D., Galil, Z., Italiano, G.F.: Improved sparsification. Information and Computer Science. University of California, Irvine (1993)
3.
Eppstein, D., Galil, Z., Italiano, G.F., Nissenzweig, A.: Sparsification - a technique for speeding up dynamic graph algorithms. J. ACM 44, 669–696 (1997)MathSciNetCrossRefMATH
4.
Eppstein, D., Galil, Z., Italiano, G.F., Spencer, T.H.: Separator based sparsification: I. Planarity testing and minimum spanning trees. J. Comput. Syst. Sci. 52(1), 3–27 (1996)MathSciNetCrossRefMATH
5.
Eppstein, D., Italiano, G.F., Tamassia, R., Tarjan, R.E., Westbrook, J., Yung, M.: Maintenance of a minimum spanning forest in a dynamic plane graph. J. Algorithms 13(1), 33–54 (1992)MathSciNetCrossRefMATH
6.
Frederickson, G.N.: Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Comput. 14(4), 781–798 (1985)MathSciNetCrossRefMATH
7.
Frederickson, G.N.: Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput. 16(6), 1004–1022 (1987)MathSciNetCrossRefMATH
8.
9.
Gustedt, J.: Efficient union-find for planar graphs and other sparse graph classes. Theor. Comput. Sci. 203(1), 123–141 (1998)MathSciNetCrossRefMATH
10.
Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM 46(4), 502–516 (1999)MathSciNetCrossRefMATH
11.
Henzinger, M.R., Fredman, M.L.: Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica 22(3), 351–362 (1998)MathSciNetCrossRefMATH
12.
Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48(4), 723–760 (2001)MathSciNetCrossRefMATH
13.
Kapron, B.M., King, V., Mountjoy, B.: Dynamic graph connectivity in polylogarithmic worst case time. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’13, pages 1131–1142. SIAM (2013)
14.
Kejlberg-Rasmussen, C., Kopelowitz, T., Pettie, S., Thorup, M.: Deterministic worst case dynamic connectivity: Simpler and faster. CoRR (2015). arXiv:1507.​05944
15.
Klein, P.N., Mozes, S., Sommer, C.: Structured recursive separator decompositions for planar graphs in linear time. In: Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 505–514. ACM (2013)
16.
17.
La Poutré, J.A.: Lower bounds for the union-find and the sp;it-find problem on pointer machines. J. Comput. Syst. Sci. 52(1), 87–99 (1996)MathSciNetCrossRefMATH
18.
19.
Tarjan, R.E.: A class of algorithms which require nonlinear time to maintain disjoint sets. J. Comput. Syst. Sci. 18(2), 110–127 (1979)MathSciNetCrossRefMATH
20.
21.
Thorup, M.: Near-optimal fully-dynamic graph connectivity. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 343–350, ACM, p 2000
22.
van Walderveen, F., Zeh, N., Arge, L.: Multiway simple cycle separators I/O-efficient algorithms for planar graphs. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 901–918. SIAM, p 2013
23.
Wulff-Nilsen, C.: Faster deterministic fully-dynamic graph connectivity. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1757–1769. SIAM, p 2013
Metadaten
Titel
Optimal Decremental Connectivity in Planar Graphs
verfasst von
Jakub Łącki
Piotr Sankowski
Publikationsdatum
20.09.2016
Verlag
Springer US
Erschienen in
Theory of Computing Systems / Ausgabe 4/2017
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-016-9709-x

Weitere Artikel der Ausgabe 4/2017

Theory of Computing Systems 4/2017 Zur Ausgabe

OriginalPaper

Short lists with short programs from programs of functions and strings

EditorialNotes

Editorial: Special Issue on “Theoretical Aspects of Computer Science” (STACS 2015)

OriginalPaper

On the Complexity of Automatic Complexity

OriginalPaper

A Generalized Characterization of Algorithmic Probability

OriginalPaper

Exact Constructive and Computable Dimensions

OriginalPaper

Conditional Probabilities and van Lambalgen’s Theorem Revisited