Sebastian Forster

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

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Fast 2-Approximate All-Pairs Shortest Paths.

Michal Dory, Sebastian Forster, Yael Kirkpatrick, Yasamin Nazari, Virginia Vassilevska Williams, Tijn de Vos

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Dynamic algorithms for <i>k</i>-center on graphs.

Emilio Cruciani, Sebastian Forster, Gramoz Goranci, Yasamin Nazari, Antonis Skarlatos

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

On Dynamic Graph Algorithms with Predictions.

Jan van den Brand, Sebastian Forster, Yasamin Nazari, Adam Polak

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths.

Michal Dory, Sebastian Forster, Yasamin Nazari, Tijn de Vos

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023

Faster Cut Sparsification of Weighted Graphs.

Sebastian Forster, Tijn de Vos

Algorithmica, April, 2023

Dynamic algorithms for k-center on graphs.

Emilio Cruciani, Sebastian Forster, Gramoz Goranci, Yasamin Nazari, Antonis Skarlatos

CoRR, 2023

Fast Algorithms for Energy Games in Special Cases.

Sebastian Forster, Antonis Skarlatos, Tijn de Vos

Proceedings of the Fourteenth International Symposium on Games, 2023

The Laplacian Paradigm in Deterministic Congested Clique.

Sebastian Forster, Tijn de Vos

CoRR, 2023

Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch.

Sebastian Forster, Yasamin Nazari, Maximilian Probst Gutenberg

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique.

Sebastian Forster, Tijn de Vos

Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, 2023

Bootstrapping Dynamic Distance Oracles.

Sebastian Forster, Gramoz Goranci, Yasamin Nazari, Antonis Skarlatos

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

Dynamic Graph Algorithms (Dagstuhl Seminar 22461).

Aaron Bernstein, Shiri Chechik, Sebastian Forster, Tsvi Kopelowitz, Yasamin Nazari, Nicole Wein

Dagstuhl Reports, November, 2022

The Laplacian Paradigm in the Broadcast Congested Clique.

Sebastian Forster, Tijn de Vos

Proceedings of the PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25, 2022

Fast Deterministic Fully Dynamic Distance Approximation.

Jan van den Brand, Sebastian Forster, Yasamin Nazari

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.

Aaron Bernstein, Sebastian Forster, Monika Henzinger

ACM Trans. Algorithms, 2021

A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.

Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai

SIAM J. Comput., 2021

Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models.

Ruben Becker, Sebastian Forster, Andreas Karrenbauer, Christoph Lenzen

SIAM J. Comput., 2021

Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications.

Sebastian Forster, Gramoz Goranci, Monika Henzinger

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions.

Sebastian Forster, Martin Grösbacher, Tijn de Vos

Proceedings of the 25th International Conference on Principles of Distributed Systems, 2021

Minor Sparsifiers and the Distributed Laplacian Paradigm.

Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun, Mingquan Ye

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.

Sebastian Forster, Danupon Nanongkai, Liu Yang, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai

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.

Sebastian Forster, Liu Yang

CoRR, 2019

Dynamic low-stretch trees via dynamic low-diameter decompositions.

Sebastian Forster, Gramoz Goranci

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.

Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai

J. ACM, 2018

A note on hardness of diameter approximation.

Karl Bringmann, Sebastian Krinninger

Inf. Process. Lett., 2018

A Faster Distributed Single-Source Shortest Paths Algorithm.

Sebastian Forster, Danupon Nanongkai

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.

Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai

ACM Trans. Algorithms, 2017

Brief Announcement: A Note on Hardness of Diameter Approximation.

Karl Bringmann, Sebastian Krinninger

Proceedings of the 31st International Symposium on Distributed Computing, 2017

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

Ittai Abraham, Shiri Chechik, Sebastian Krinninger

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Decremental Data Structures for Connectivity and Dominators in Directed Graphs.

Loukas Georgiadis, Thomas Dueholm Hansen, Giuseppe F. Italiano, Sebastian Krinninger, Nikos Parotsidis

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.

Karl Bringmann, Thomas Dueholm Hansen, Sebastian Krinninger

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.

Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai

Encyclopedia of Algorithms, 2016

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

Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai

SIAM J. Comput., 2016

Approximate Undirected Transshipment and Shortest Paths via Gradient Descent.

Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, Christoph Lenzen

CoRR, 2016

On Fully Dynamic Graph Sparsifiers.

Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, Richard Peng

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Fully Dynamic Spanners with Worst-Case Update Time.

Greg Bodwin, Sebastian Krinninger

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015

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

Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai

CoRR, 2015

Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture.

Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, Thatchaphol Saranurak

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs.

Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time.

Monika Henzinger, Sebastian Krinninger, Veronika Loitzenbauer

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Schnellere Approximationsalgorithmen zur Partiell-Dynamischen Berechnung Kürzester Wege.

Sebastian Krinninger

Proceedings of the Ausgezeichnete Informatikdissertationen 2015, 2015

2014

Approximating the minimum cycle mean.

Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger, Veronika Loitzenbauer, Michael A. Raskin

Theor. Comput. Sci., 2014

Validity in a logic that combines supervaluation and fuzzy logic based theories of vagueness.

Sebastian Krinninger

Fuzzy Sets Syst., 2014

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

Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai

Algorithmica, 2014

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

Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai

Proceedings of the Symposium on Theory of Computing, 2014

A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths.

Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2013

Approximating the minimum cycle mean.

Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger, Veronika Loitzenbauer

Proceedings of the Proceedings Fourth International Symposium on Games, 2013

Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks.

Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2010

Online Signature Verification With Support Vector Machines Based on LCSS Kernel Functions.

Christian Gruber, Thiemo Gruber, Sebastian Krinninger, Bernhard Sick

IEEE Trans. Syst. Man Cybern. Part B, 2010