Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Improved data structures for fully dynamic biconnectivity
 
Loading...
Thumbnail Image
research article

Improved data structures for fully dynamic biconnectivity

Henzinger, Monika R.  
2000
SIAM Journal on Computing

We present fully dynamic algorithms for maintaining the biconnected components in general and plane graphs. A fully dynamic algorithm maintains a graph during a sequence of insertions and deletions of edges or isolated vertices. Let m be the number of edges and n be the number of vertices in a graph. The time per operation of the best deterministic algorithms is O(sqrt(n)) in general graphs and O(log n) in plane graphs for fully dynamic connectivity and O(minm2/3, n) in general graphs and O(sqrt(n)) in plane graphs for fully dynamic biconnectivity. We improve the later running times to O(sqrt(m.log(n)) in general graphs and O(log2 n) in plane graphs. Our algorithm for general graphs can also find the biconnected components of all vertices in time O(n).

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

Henzinger00-Improved.pdf

Access type

openaccess

Size

425.62 KB

Format

Adobe PDF

Checksum (MD5)

27f6ec36c517333a202774f0eaf1f822

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés