Optimal on-line decremental connectivity in trees

DOI10.1016/S0020-0190(97)00170-1zbMATH Open1337.68080OpenAlexW1969221581MaRDI QIDQ290266FDOQ290266

Authors: Stephen Alstrup, Jens Peter Secher, Maz Spork 

Publication date: 1 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(97)00170-1

Recommendations

• Decremental Dynamic Connectivity
• Dynamic 2- and 3-connectivity on planar graphs
• Optimal decremental connectivity in planar graphs
• Optimal decremental connectivity in planar graphs
• An Optimal Rebuilding Strategy for a Decremental Tree Problem

zbMATH Keywords

algorithmstreesconnectivity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Cites Work

• Title not available (Why is that?)
• A linear-time algorithm for a special case of disjoint set union
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• An On-Line Edge-Deletion Problem
• Title not available (Why is that?)
• Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
• Title not available (Why is that?)

Cited In (8)

• Title not available (Why is that?)
• An Optimal Rebuilding Strategy for a Decremental Tree Problem
• Binary jumbled pattern matching on trees and tree-like structures
• Optimal decremental connectivity in planar graphs
• Succinct data structures for nearest colored node in a tree
• Decremental Dynamic Connectivity
• Faster Online Elastic Degenerate String Matching
• On Cartesian trees and range minimum queries

This page was built for publication: Optimal on-line decremental connectivity in trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q290266)