Tamás Lukovszki, Willy-B. Strothman  Home/Search
Context
Related
| unipaderborn.de/f...TRri97186.ps.gz wwwhni.unipaderborn.de/...tamas1.ps.gz unipaderborn.de/~a...DecBiPlanar.ps.gz Cached: PS.gz PS PDF DjVu Image Update Help From: unipaderborn.de/fachbereich/A... (more) From: hni.unipaderborn....parallel_pub (Enter author homepages) |
Rate this article:      (best)Comment on this article |
Abstract: : In this paper we present a (randomized) algorithm for maintaining the biconnected components of a dynamic planar graph of n vertices under deletions of edges. The biconnected components can be maintained under any sequence of edge deletions in a total of O(n log n) time, with high probability. This gives O(logn) amortized time per edge deletion, which improves previous (deterministic) results from [6] due to Giammarresi and Italiano, where O(n log 2 n) amortized time is needed. Our work... (Update)
Similar documents (at the sentence level):
14.9%: Bounded Degree Spanning Trees - Strothmann (Correct)
Active bibliography (related documents): More All
0.5: An Experimental Study of Dynamic Algorithms for.. - Frigioni, Miller.. (2000) (Correct)
0.3: Separator-Based Sparsification II: Edge And Vertex.. - Eppstein, Galil.. (1998) (Correct)
0.2: Certificates and Fast Algorithms for Biconnectivity in.. - Henzinger, Poutré (1997) (Correct)
Similar documents based on text: More All
0.4: Improved Algorithms for Maintaining Transitive Closure.. - Baswana, Hariharan, Sen (2001) (Correct)
0.2: Poly-logarithmic deterministic fully-dynamic graph.. - Holm, de Lichtenberg, .. (1998) (Correct)
0.2: A Partial Report on Parallel Graph Algorithms (EE 382L term.. - Hsu, Patra, Yang (Correct)
BibTeX entry: (Update)
@misc{ lukovszki-decremental,
author = "Tamás Lukovszki and Willy-B. Strothman",
title = "Decremental Biconnectivity on Planar Graphs",
url = "citeseer.nj.nec.com/lukovszki97decremental.html" }
Citations (may not include all citations):1257 The Design and Analysis of Computer Algorithms (context) - Aho, Hopcroft et al. - 1974
223 Primitives for the Manipulation of General Subdivisions and .. (context) - Guibas, Stolfi - 1985
94 Sparsification --- A Technique for Speeding up Dynamic Algor.. (context) - Eppstein, Galil et al. - 1996
39 Maintaining Bridge-Connected and Biconnected Components On-l.. (context) - Westbrook, Tarjan - 1992
31 Improved Data Structures for Fully Dynamic Biconnectivity (context) - Rauch
22 Fully Dynamic Biconnectivity and Transitive Closure (context) - Henzinger, King - 1995
14 Dynamic Graph Algorithms and Data Structures (context) - Poutr'e - 1991
9 Certificates and Fast Algorithms for Biconnectivity in Fully.. - Henzinger, Poutr'e - 1995
4 Decremental 2- and 3-Connectivity on Planar Graphs (context) - Giammarresi, Italiano - 1996
2 Bounded Degree Spanning Trees - Czumaj, Strothmann
2 CRC Handbook of Algorithms and Theory of Computation (context) - Eppstein, Galil et al. - 1997
1 Informatik: Festschrift zum 60: Geburtstag von Gunter Hotz (context) - Dietzfelbinger, auf et al. - 1992
Documents on the same site (http://www.uni-paderborn.de/fachbereich/AG/agmadh/WWW/DFG-SPP/): More
Bounded Degree Spanning Trees (Extended abstract) - Czumaj, Strothmann (Correct)
New Results on Fault Tolerant Geometric Spanners - Lukovszki (1999) (Correct)
Bounded Degree Spanning Trees (Extended abstract) - Czumaj, Strothmann (Correct)
Online articles have much greater impact More about CiteSeer Add search form to your site Submit documents Feedback
CiteSeer - citeseer.org - Terms of Service - Privacy Policy - Copyright © 1997-2002 NEC Research Institute