Optimal on-line decremental connectivity in trees

DOI10.1016/S0020-0190(97)00170-1zbMath1337.68080OpenAlexW1969221581MaRDI QIDQ290266

Stephen Alstrup, Maz Spork, Jens Peter Secher

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

zbMATH Keywords

algorithmsconnectivitytrees

Mathematics Subject Classification ID

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

Related Items (7)

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 ⋮ Compressed subsequence matching and packed tree coloring ⋮ On Cartesian trees and range minimum queries ⋮ Unnamed Item ⋮ Faster Online Elastic Degenerate String Matching

Cites Work

• 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
• Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
• Unnamed Item
• Unnamed Item
• Unnamed Item

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