On the computational complexity of dynamic graph problems

DOI10.1016/0304-3975(95)00079-8zbMath0871.68098OpenAlexW2049354208MaRDI QIDQ1351463

G. Ramalingam, Thomas W. Reps

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00079-8

zbMATH Keywords

incremental algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (26)

Optimization of spatial complex networks ⋮ On competitive on-line algorithms for the dynamic priority-ordering problem ⋮ On the computational complexity of dynamic graph problems ⋮ Dynamic shortest paths and transitive closure: algorithmic techniques and data structures ⋮ Improving the Betweenness Centrality of a Node by Adding Links ⋮ On the complexity of average path length for biological networks and patterns ⋮ Certified Graph View Maintenance with Regular Datalog ⋮ Two-level heaps: a new priority queue structure with applications to the single source shortest path problem ⋮ A fully dynamic algorithm for distributed shortest paths. ⋮ A dynamic topological sort algorithm for directed acyclic graphs ⋮ Average update times for fully-dynamic all-pairs shortest paths ⋮ Average-Case Analysis of Online Topological Ordering ⋮ Incremental qualitative temporal reasoning: Algorithms for the point algebra and the ORD-Horn class ⋮ Tiers for peers: a practical algorithm for discovering hierarchy in weighted networks ⋮ A formal verification technique for behavioural model-to-model transformations ⋮ Incremental problems in the parameterized complexity setting ⋮ Average-case analysis of incremental topological ordering ⋮ Partially dynamic efficient algorithms for distributed shortest paths ⋮ Fully dynamic all pairs shortest paths with real edge weights ⋮ A single-source shortest path algorithm for dynamic graphs ⋮ Dynamic Maintenance of a Shortest-Path Tree on Homogeneous Batches of Updates ⋮ Semi-dynamic breadth-first search in digraphs ⋮ Algorithmic Techniques for Maintaining Shortest Routes in Dynamic Networks ⋮ Dynamically Maintaining Shortest Path Trees under Batches of Updates ⋮ Lifelong planning \(\text{A}^*\) ⋮ Maintaining longest paths incrementally

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Properties of data flow frameworks: A unified model
• Proving relative lower bounds for incremental algorithms
• On incremental evaluation of ordered attributed grammars
• Incremental evaluation for attribute grammars with unrestricted movement between tree modifications
• A topological approach to dynamic graph connectivity
• Conditions for incremental iteration: Examples and counterexamples
• On the computational complexity of dynamic graph problems
• Netzwerk-Veränderungen und Korrektur kürzester Weglängen von einer Wurzelmenge zu allen anderen Knoten
• Bounded incremental computation
• Time polynomial in input or output
• An On-Line Edge-Deletion Problem
• Graph Property Update Algorithms and Their Appligation to Distance Matrices
• On Finding and Updating Spanning Trees and Shortest Paths
• Etude Et Extension D’Un Algorithme De Murghland
• A new shortest path updating algorithm
• The parametric problem of shortest distances

This page was built for publication: On the computational complexity of dynamic graph problems