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

DOI10.1137/S0097539792226825zbMATH Open0874.68081DBLPjournals/siamcomp/Frederickson97OpenAlexW2104224360WikidataQ56077950 ScholiaQ56077950MaRDI QIDQ4337633FDOQ4337633

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

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

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)

Cited In (15)

• Succinct indices for path minimum, with applications
• Maintaining dynamic minimum spanning trees: an experimental study
• A survey on combinatorial optimization in dynamic environments
• Optimal on-line decremental connectivity in trees
• Longest common extensions in trees
• Partial order multiway search
• Title not available (Why is that?)
• Good \(r\)-divisions imply optimal amortized decremental biconnectivity
• The saga of minimum spanning trees
• 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
• The Effect of Planarization on Width
• Listing the bonds of a graph in \(\widetilde{O} (n)\)-delay

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)