Optimal on-line decremental connectivity in trees

DOI10.1016/S0020-0190(97)00170-1MaRDI QIDQ290266zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

algorithmstreesconnectivity

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 432790 (Why is no real title available?)
• scientific article; zbMATH DE number 1263228 (Why is no real title available?)
• scientific article; zbMATH DE number 6472605 (Why is no real title available?)
• A linear-time algorithm for a special case of disjoint set union
• Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
• An On-Line Edge-Deletion Problem
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications

Cited in

(8)

• scientific article; zbMATH DE number 7286689 (Why is no real title available?)
• 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)