Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. (Q5874499)

scientific article; zbMATH DE number 7651170

Language	Label	Description	Also known as
English	Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.	scientific article; zbMATH DE number 7651170

Statements

instance of

scholarly article

0 references

author

Panagiotis Charalampopoulos

0 references

Adam Karczmarz

0 references

publication date

7 February 2023

0 references

zbMATH Keywords

dynamic graph algorithms

0 references

planar graphs

0 references

single-source shortest paths

0 references

strong connectivity

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://drops.dagstuhl.de/opus/volltexte/2020/12897/pdf/LIPIcs-ESA-2020-31.pdf/

0 references

title

Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. (English)

0 references

cites work

On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs

0 references

Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels

0 references

Fully dynamic all-pairs shortest paths with worst-case update-time revisited

0 references

Q3138872

0 references

Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths

0 references

A New Approach to Incremental Cycle Detection and Related Problems

0 references

Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs

0 references

Q5111375

0 references

Deterministic decremental single source shortest paths: beyond the o(mn) bound

0 references

Deterministic Partially Dynamic Single Source Shortest Paths for Sparse Graphs

0 references

Decremental strongly-connected components and single-source reachability in near-linear time

0 references

An O ( n log n ) algorithm for maximum st -flow in a directed planar graph

0 references

Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time

0 references

Min st -Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time

0 references

Many distances in planar graphs

0 references

Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs

0 references

Multiple-Source Shortest Paths in Embedded Graphs

0 references

Faster approximate diameter and distance oracles in planar graphs

0 references

Almost optimal distance oracles for planar graphs

0 references

Approximate Distance Oracles with Improved Bounds

0 references

Shortest path queries in planar graphs

0 references

A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems

0 references

A new approach to dynamic all pairs shortest paths

0 references

Dynamic Plane Transitive Closure

0 references

Separator based sparsification. I: Planarity testing and minimum spanning trees

0 references

Maintenance of a minimum spanning forest in a dynamic plane graph

0 references

Holiest minimum-cost paths and flows in surface graphs

0 references

An On-Line Edge-Deletion Problem

0 references

Planar graphs, negative weight edges, shortest paths, and near linear time

0 references

Fast Algorithms for Shortest Paths in Planar Graphs, with Applications

0 references

Q5002738

0 references

Constant Query Time $$(1+\epsilon )$$ -Approximate Distance Oracle for Planar Graphs

0 references

New algorithms and hardness for incremental single-source shortest paths in directed graphs

0 references

Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary

0 references

Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler

0 references

Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds

0 references

Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance

0 references

Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs

0 references

Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization

0 references

Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity

0 references

Fully Dynamic Connectivity in O(log n(log log n)2) Amortized Expected Time

0 references

Decremental single-source reachability in planar digraphs

0 references

Improved algorithms for min cut and max flow in undirected planar graphs

0 references

Dynamic graph connectivity in polylogarithmic worst case time

0 references

Q4607877

0 references

Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs

0 references

More Compact Oracles for Approximate Distances in Undirected Planar Graphs

0 references

Q4829018

0 references

Q2921664

0 references

Structured recursive separator decompositions for planar graphs in linear time

0 references

Shortest paths in directed planar graphs with negative lengths

0 references

A fully dynamic approximation scheme for shortest paths in planar graphs

0 references

Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms

0 references

Q5743390

0 references

Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time

0 references

On dynamic shortest paths problems

0 references

Computing and Combinatorics

0 references

Compact oracles for reachability and approximate distances in planar digraphs

0 references

Algorithm Theory - SWAT 2004

0 references

Worst-case update times for fully-dynamic all-pairs shortest paths

0 references

Approximate distance oracles

0 references

Approximate Distance Oracles with Improved Query Time

0 references

Faster Deterministic Fully-Dynamic Graph Connectivity

0 references

Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff

0 references

Identifiers

DOI

10.4230/LIPIcs.ESA.2020.31

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5874499