Back to homepage

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