Recent Advances in Fully Dynamic Graph Algorithms – A Quick Reference Guide

DOI10.1145/3555806MaRDI QIDQ6127820zbMATH OpenFDO

Authors Kathrin Hanauer, Monika R. Henzinger, Christian Schulz

Publication date 14 April 2024

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.11169

zbMATH Keywords

dynamic algorithmsgraph algorithms

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: In recent years, significant advances have been made in the design and analysis of fully dynamic algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. Here, we present a quick reference guide to recent engineering and theory results in the area of fully dynamic graph algorithms.

Recommendations

• scientific article; zbMATH DE number 1956218
• A single-source shortest path algorithm for dynamic graphs
• Randomization for efficient dynamic graph algorithms (invited talk)
• Semi-dynamic algorithms for strongly chordal graphs

Cited in

(7)

• A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges
• Hardness of dynamic core and truss decompositions
• Streaming graph algorithms in the massively parallel computation model
• Temporal queries for dynamic temporal forests
• The parallel dynamic complexity of the abelian Cayley group membership problem
• Optimization of the directed spanning trees using the weighted matroid intersection algorithm
• Finding conflict-free minimum weight spanning trees using maximal stable sets of the conflict graph

This page was built for publication: Recent Advances in Fully Dynamic Graph Algorithms – A Quick Reference Guide

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