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 (13)

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

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