Sebastian Forster

Orcid: 0000-0002-2191-3381

Affiliations:
  • University of Salzburg, Austria


According to our database1, Sebastian Forster authored at least 49 papers between 2010 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Fast 2-Approximate All-Pairs Shortest Paths.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Dynamic algorithms for <i>k</i>-center on graphs.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

On Dynamic Graph Algorithms with Predictions.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths.
Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023
Faster Cut Sparsification of Weighted Graphs.
Algorithmica, April, 2023

Dynamic algorithms for k-center on graphs.
CoRR, 2023

Fast Algorithms for Energy Games in Special Cases.
Proceedings of the Fourteenth International Symposium on Games, 2023

The Laplacian Paradigm in Deterministic Congested Clique.
CoRR, 2023

Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique.
Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, 2023

Bootstrapping Dynamic Distance Oracles.
Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022
Dynamic Graph Algorithms (Dagstuhl Seminar 22461).
Dagstuhl Reports, November, 2022

The Laplacian Paradigm in the Broadcast Congested Clique.
Proceedings of the PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25, 2022

Fast Deterministic Fully Dynamic Distance Approximation.
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.
ACM Trans. Algorithms, 2021

A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.
SIAM J. Comput., 2021

Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models.
SIAM J. Comput., 2021

Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions.
Proceedings of the 25th International Conference on Principles of Distributed Systems, 2021

Minor Sparsifiers and the Distributed Laplacian Paradigm.
Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019
A Faster Local Algorithm for Detecting Bounded-Size Cuts with Applications to Higher-Connectivity Problems.
CoRR, 2019

Dynamic low-stretch trees via dynamic low-diameter decompositions.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

2018
Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time.
J. ACM, 2018

A note on hardness of diameter approximation.
Inf. Process. Lett., 2018

A Faster Distributed Single-Source Shortest Paths Algorithm.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017
Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks.
ACM Trans. Algorithms, 2017

Brief Announcement: A Note on Hardness of Diameter Approximation.
Proceedings of the 31st International Symposium on Distributed Computing, 2017

Fully dynamic all-pairs shortest paths with worst-case update-time revisited.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Decremental Data Structures for Connectivity and Dominators in Directed Graphs.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016
Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrierand Derandomization.
Encyclopedia of Algorithms, 2016

Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization.
SIAM J. Comput., 2016

Approximate Undirected Transshipment and Shortest Paths via Gradient Descent.
CoRR, 2016

On Fully Dynamic Graph Sparsifiers.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Fully Dynamic Spanners with Worst-Case Update Time.
Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015
An Almost-Tight Distributed Algorithm for Computing Single-Source Shortest Paths.
CoRR, 2015

Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Schnellere Approximationsalgorithmen zur Partiell-Dynamischen Berechnung Kürzester Wege.
Proceedings of the Ausgezeichnete Informatikdissertationen 2015, 2015

2014
Approximating the minimum cycle mean.
Theor. Comput. Sci., 2014

Validity in a logic that combines supervaluation and fuzzy logic based theories of vagueness.
Fuzzy Sets Syst., 2014

Polynomial-Time Algorithms for Energy Games with Special Weight Structures.
Algorithmica, 2014

Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs.
Proceedings of the Symposium on Theory of Computing, 2014

A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2013
Approximating the minimum cycle mean.
Proceedings of the Proceedings Fourth International Symposium on Games, 2013

Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2010
Online Signature Verification With Support Vector Machines Based on LCSS Kernel Functions.
IEEE Trans. Syst. Man Cybern. Part B, 2010


  Loading...