Publications of Sebastian Forster
Sebastian Forster previously published under the name Sebastian Krinninger. Unless stated otherwise, author names are given in alphabetic order.
Journal Articles
- A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
Aaron Bernstein, Sebastian Forster, and Monika Henzinger
Transactions on Algorithms 17(4), pp. 29:1–29:51, 2021
arXiv - A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
SIAM Journal on Computing 50(3), pp. STOC16-98–STOC16-137, 2021
(STOC 2016 Special Issue)
arXiv - Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
Ruben Becker, Sebastian Forster, Andreas Karrenbauer, and Christoph Lenzen
SIAM Journal on Computing 50(3), pp. 815–856, 2021
arXiv - Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
Journal of the ACM 65(6), pp. 36:1–36:40, 2018
arXiv - A note on hardness of diameter approximation
Karl Bringmann and Sebastian Krinninger
Information Processing Letters 133, pp. 10–15, 2018
arXiv - Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
Transactions on Algorithms 13(4), p. 51:1-51:24, 2017
(Journal version of ICALP 2013 paper)
arXiv - Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
SIAM Journal on Computing 45(3), pp. 947–1006, 2016
(FOCS 2013 Special Issue)
arXiv - Polynomial-Time Algorithms for Energy Games with Special Weight Structures
Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
Algorithmica 70(3), pp. 457–492, 2014
(ESA 2012 Special Issue)
arXiv - Approximating the minimum cycle mean
Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger, Veronika Loitzenbauer, and Michael A. Raskin
Theoretical Computer Science 547, pp. 104–116, 2014
(Journal version of GandALF 2013 paper)
Preprint - Validity in a logic that combines supervaluation and fuzzy logic based theories of vagueness
Sebastian Krinninger
Fuzzy Sets and Systems 247, pp. 1–17, 2014
Preprint - Online Signature Verification With Support Vector Machines Based on LCSS Kernel Functions
Christian Gruber, Thiemo Gruber, Sebastian Krinninger, and Bernhard Sick
IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics 40(4):1088-1100, 2010
(Author names are NOT given in alphabetic order.)
Conference Papers
- Fast Deterministic Fully Dynamic Distance Approximation
Jan van den Brand, Sebastian Forster, and Yasamin Nazari
63rd IEEE Symposium on Foundations of Computer Science (FOCS), 2022 arXiv - The Laplacian Paradigm in the Broadcast Congested Clique
Sebastian Forster and Tijn de Vos
41st ACM Symposium on Principles of Distributed Computing (PODC), 2022
arXiv - Faster Cut Sparsification of Weighted Graphs
Sebastian Forster and Tijn de Vos
49th EATCS International Colloquium on Automata, Languages, and Programming (ICALP), 2022
arXiv - Minor Sparsifiers and the Distributed Laplacian Paradigm
Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun, and Mingquan Ye
62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2022
arXiv - An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions
Sebastian Forster, Martin Grösbacher, and Tijn de Vos
Conference on Principles of Distributed Systems (OPODIS), 2021
arXiv - Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications
Sebastian Forster, Gramoz Goranci, and Monika Henzinger
32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021
arXiv - Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
Sebastian Forster, Danupon Nanongkai, Thatchaphol Saranurak, Liu Yang, and Sorrachai Yingchareonthawornchai
31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020
arXiv - Dynamic Low-Stretch Trees via Dynamic Low-Diameter Decompositions
Sebastian Forster and Gramoz Goranci
51st Annual ACM Symposium on the Theory of Computing (STOC), 2019
arXiv - A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
Aaron Bernstein, Sebastian Forster, and Monika Henzinger
30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019
arXiv - A Faster Distributed Single-Source Shortest Paths Algorithm
Sebastian Forster and Danupon Nanongkai
59th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2018
arXiv - Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen
31st International Symposium on Distributed Computing (DISC), 2017
arXiv - Brief Announcement: A Note on Hardness of Diameter Approximation
Karl Bringmann and Sebastian Krinninger
31st International Symposium on Distributed Computing (DISC), 2017
arXiv - Decremental Data Structures for Connectivity and Dominators in Directed Graphs
Loukas Georgiadis, Thomas Dueholm Hansen, Giuseppe F. Italiano, Sebastian Krinninger, and Nikos Parotsidis
44th International Colloquium on Automata, Languages, and Programming (ICALP), 2017
arXiv - Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs
Karl Bringmann, Thomas Dueholm Hansen, and Sebastian Krinninger
44th International Colloquium on Automata, Languages, and Programming (ICALP), 2017
arXiv - Fully dynamic all-pairs shortest paths with worst-case update-time revisited
Ittai Abraham, Shiri Chechik, and Sebastian Krinninger
28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017
arXiv - On Fully Dynamic Graph Sparsifiers
Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng
57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2016.
arXiv - Fully Dynamic Spanners with Worst-Case Update Time
Greg Bodwin and Sebastian Krinninger
24th Annual European Symposium on Algorithms (ESA), 2016.
arXiv - A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
48th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2016.
(Invited to STOC 2016 Special Issue of SIAM Journal on Computing)
arXiv - Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time
Monika Henzinger, Sebastian Krinninger, and Veronika Loitzenbauer
42nd International Colloquium on Automata, Languages and Programming (ICALP), 2015.
arXiv - Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
42nd International Colloquium on Automata, Languages and Programming (ICALP), 2015.
arXiv - Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak
47th Annual ACM Symposium on Theory of Computing (STOC), 2015.
arXiv - Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
55th IEEE Symposium on Foundations of Computer Science (FOCS), 2014.
arXiv - Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
46th Annual ACM Symposium on Theory of Computing (STOC), 2014.
arXiv - A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014
Preprint - Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2013
(Invited to FOCS 2013 Special Issue of SIAM Journal on Computing)
arXiv - Approximating the minimum cycle mean
Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger, and Veronika Loitzenbauer
Fourth International Symposium on Games, Automata, Logics and Formal Verification (GandALF), 2013
- Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
40th International Colloquium on Automata, Languages and Programming (ICALP), 2013
arXiv - Polynomial-Time Algorithms for Energy Games with Special Weight Structures
Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
20th Annual European Symposium on Algorithms (ESA), 2012
(Invited to ESA 2012 Special Issue of Algorithmica)
arXiv - A Global Satellite Link Sensor Network
Bastian Preindl, Lars Mehnen, Frank Rattay, Jens Dalsgaard Nielsen, Sebastian Krinninger, and Kresten Kjær Sørensen
8th Annual IEEE Conference on Sensors (SENSORS), 2009
(Author names are NOT given in alphabetic order.)
Other Publications
- Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
Encyclopedia of Algorithms 600–602, 2016 - Schnellere Algorithmen zur partiell-dynamischen Berechnung Kürzester Wege
Sebastian Krinninger
Ausgezeichnete Informatikdissertationen 2015, GI-Edition: Lecture Notes in Informatics
(A summary of my PhD thesis in German)
Preprint