scientific article; zbMATH DE number 432745

MaRDI QIDQ3138871zbMATH OpenFDO

Authors David Eppstein, Giuseppe F. Italiano, Roberto Tamassia, Robert E. Tarjan, Jeffery R. Westbrook, Moti Yung

Publication date 2 January 1994

zbMATH Keywords

minimum spanning forestdynamic planar graph

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cited in

(14)

• Bipartite graphs, upward drawings, and planarity
• Fully dynamic biconnectivity in graphs
• Finding the k smallest spanning trees
• Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time
• Fully dynamic 2-edge-connectivity in planar graphs
• Data structures for two-edge connectivity in planar graphs
• Average case analysis of dynamic geometric optimization
• Maintenance of triconnected components of graphs
• Average case analysis of fully dynamic reachability for directed graphs
• Dynamic algorithms for shortest paths in planar graphs
• Average case analysis of fully dynamic connectivity for directed graphs
• Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm
• Finding the \(k\) smallest spanning trees
• Reachability preserving compression for dynamic graph

This page was built for publication:

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