Optimal MST Maintenance for Transient Deletion of Every Node in Planar Graphs

DOI10.1007/3-540-45071-8_41MaRDI QIDQ3082947zbMATH OpenOpenAlexFDO

Authors Carlo Gaibisso, Guido Proietti, Richard B. Tan

Publication date 18 March 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-45071-8_41

zbMATH Keywords

minimum spanning treeplanar graphsradio networks survivabilitytransient node failures

Mathematics Subject Classification ID

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

Recommendations

• Nearly linear time minimum spanning tree maintenance for transient node failures
• Maintenance of a minimum spanning forest in a dynamic plane graph
• scientific article; zbMATH DE number 2079363
• Dynamic maintenance of planar digraphs, with applications
• A unified approximation algorithm for node-deletion problems
• Maintaining shortest paths under deletions in weighted directed graphs
• A new approach for approximating node deletion problems
• Maintaining shortest paths under deletions in weighted directed graphs
• Approximating node-weighted \(k\)-MST on planar graphs
• Approximating node-weighted \(k\)-MST on planar graphs

Cited in

(2)

• Nearly linear time minimum spanning tree maintenance for transient node failures
• scientific article; zbMATH DE number 1670672 (Why is no real title available?)

This page was built for publication: Optimal MST Maintenance for Transient Deletion of Every Node in Planar Graphs

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