Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees

DOI10.1137/S0097539792226825MaRDI QIDQ4337633zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Greg N. Frederickson

Publication date 26 May 1997

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539792226825

zbMATH Keywords

2-edge-connectivityanalysis of algorithmsdata structuresembedded planar graphfully persistent data structuresk smallest spanning treesminimum spanning treeon-line updatingtopology tree

Mathematics Subject Classification ID

Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Data structures for two-edge connectivity in planar graphs
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Maintenance of 2- and 3-edge-connected components of graphs. I

Cited in

(20)

• Dynamic path queries in linear space
• String indexing for top-\(k\) close consecutive occurrences
• Succinct indices for path minimum, with applications
• Gapped indexing for consecutive occurrences
• Optimal on-line decremental connectivity in trees
• A survey on combinatorial optimization in dynamic environments
• Longest common extensions in trees
• scientific article; zbMATH DE number 1471729 (Why is no real title available?)
• The saga of minimum spanning trees
• Maintaining centdians in a fully dynamic forest with top trees
• The effect of planarization on width
• Listing the bonds of a graph in \(\widetilde{O} (n)\)-delay
• Partial order multiway search
• Good \(r\)-divisions imply optimal amortized decremental biconnectivity
• String indexing for top-\(k\) close consecutive occurrences
• On calculation of the stability radius for a minimum spanning tree
• Maintaining \(\mathrm{CMSO}_2\) properties on dynamic structures with bounded feedback vertex number
• Good r-divisions imply optimal amortized decremental biconnectivity
• Tree-packing revisited: faster fully dynamic min-cut and arboricity
• Maintaining dynamic minimum spanning trees: an experimental study

This page was built for publication: Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees

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