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

minimum spanning treeanalysis of algorithmsdata structures2-edge-connectivityembedded planar graphfully persistent data structuresk smallest spanning treeson-line updatingtopology tree

Mathematics Subject Classification ID

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

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)

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

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)