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

DOI10.1137/S0097539792226825zbMath0874.68081OpenAlexW2104224360WikidataQ56077950 ScholiaQ56077950MaRDI QIDQ4337633

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

analysis of algorithmsdata structuresminimum spanning tree2-edge-connectivityembedded planar graphfully persistent data structuresk smallest spanning treeson-line updatingtopology tree

Mathematics Subject Classification ID

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

Related Items

Succinct indices for path minimum, with applications, Optimal on-line decremental connectivity in trees, Longest common extensions in trees, A survey on combinatorial optimization in dynamic environments, String indexing for top-\(k\) close consecutive occurrences, Listing the bonds of a graph in \(\widetilde{O} (n)\)-delay, Gapped indexing for consecutive occurrences, Unnamed Item, The saga of minimum spanning trees, Maintaining centdians in a fully dynamic forest with top trees, Maintaining dynamic minimum spanning trees: an experimental study, The Effect of Planarization on Width, Dynamic path queries in linear space