![](https://dblp.dagstuhl.de/img/logo.ua.320x120.png)
![](https://dblp.dagstuhl.de/img/dropdown.dark.16x16.png)
![](https://dblp.dagstuhl.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
![search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
default search action
Sebastian Forster
Person information
- affiliation: University of Salzburg, Austria
Refine list
![note](https://dblp.dagstuhl.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
Journal Articles
- 2023
- [j12]Sebastian Forster, Tijn de Vos
:
Faster Cut Sparsification of Weighted Graphs. Algorithmica 85(4): 929-964 (2023) - 2021
- [j11]Ruben Becker
, Sebastian Forster
, Andreas Karrenbauer, Christoph Lenzen:
Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. SIAM J. Comput. 50(3): 815-856 (2021) - [j10]Monika Henzinger
, Sebastian Krinninger
, Danupon Nanongkai:
A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths. SIAM J. Comput. 50(3) (2021) - [j9]Aaron Bernstein, Sebastian Forster
, Monika Henzinger
:
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching. ACM Trans. Algorithms 17(4): 29:1-29:51 (2021) - 2018
- [j8]Karl Bringmann, Sebastian Krinninger
:
A note on hardness of diameter approximation. Inf. Process. Lett. 133: 10-15 (2018) - [j7]Monika Henzinger
, Sebastian Krinninger
, Danupon Nanongkai:
Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time. J. ACM 65(6): 36:1-36:40 (2018) - 2017
- [j6]Monika Henzinger
, Sebastian Krinninger
, Danupon Nanongkai:
Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks. ACM Trans. Algorithms 13(4): 51:1-51:24 (2017) - 2016
- [j5]Monika Henzinger
, Sebastian Krinninger
, Danupon Nanongkai:
Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization. SIAM J. Comput. 45(3): 947-1006 (2016) - 2014
- [j4]Krishnendu Chatterjee, Monika Henzinger
, Sebastian Krinninger
, Danupon Nanongkai:
Polynomial-Time Algorithms for Energy Games with Special Weight Structures. Algorithmica 70(3): 457-492 (2014) - [j3]Sebastian Krinninger
:
Validity in a logic that combines supervaluation and fuzzy logic based theories of vagueness. Fuzzy Sets Syst. 247: 1-17 (2014) - [j2]Krishnendu Chatterjee
, Monika Henzinger
, Sebastian Krinninger
, Veronika Loitzenbauer, Michael A. Raskin
:
Approximating the minimum cycle mean. Theor. Comput. Sci. 547: 104-116 (2014) - 2010
- [j1]Christian Gruber, Thiemo Gruber, Sebastian Krinninger
, Bernhard Sick
:
Online Signature Verification With Support Vector Machines Based on LCSS Kernel Functions. IEEE Trans. Syst. Man Cybern. Part B 40(4): 1088-1100 (2010)
Conference and Workshop Papers
- 2024
- [c36]Michal Dory, Sebastian Forster, Yasamin Nazari
, Tijn de Vos:
New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths. ICALP 2024: 58:1-58:19 - [c35]Emilio Cruciani, Sebastian Forster, Gramoz Goranci, Yasamin Nazari
, Antonis Skarlatos:
Dynamic algorithms for k-center on graphs. SODA 2024: 3441-3462 - [c34]Jan van den Brand
, Sebastian Forster, Yasamin Nazari
, Adam Polak
:
On Dynamic Graph Algorithms with Predictions. SODA 2024: 3534-3557 - [c33]Michal Dory, Sebastian Forster, Yael Kirkpatrick, Yasamin Nazari
, Virginia Vassilevska Williams, Tijn de Vos:
Fast 2-Approximate All-Pairs Shortest Paths. SODA 2024: 4728-4757 - 2023
- [c32]Sebastian Forster, Gramoz Goranci, Yasamin Nazari
, Antonis Skarlatos:
Bootstrapping Dynamic Distance Oracles. ESA 2023: 50:1-50:16 - [c31]Sebastian Forster
, Tijn de Vos
:
Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique. PODC 2023: 75-78 - [c30]Sebastian Forster, Yasamin Nazari
, Maximilian Probst Gutenberg
:
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch. STOC 2023: 1173-1186 - [c29]Sebastian Forster, Antonis Skarlatos, Tijn de Vos
:
Fast Algorithms for Energy Games in Special Cases. GandALF 2023: 236-252 - 2022
- [c28]Jan van den Brand
, Sebastian Forster, Yasamin Nazari
:
Fast Deterministic Fully Dynamic Distance Approximation. FOCS 2022: 1011-1022 - [c27]Sebastian Forster, Tijn de Vos
:
Faster Cut Sparsification of Weighted Graphs. ICALP 2022: 61:1-61:19 - [c26]Sebastian Forster, Tijn de Vos
:
The Laplacian Paradigm in the Broadcast Congested Clique. PODC 2022: 335-344 - 2021
- [c25]Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun, Mingquan Ye:
Minor Sparsifiers and the Distributed Laplacian Paradigm. FOCS 2021: 989-999 - [c24]Sebastian Forster, Martin Grösbacher, Tijn de Vos
:
An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions. OPODIS 2021: 16:1-16:17 - [c23]Sebastian Forster
, Gramoz Goranci, Monika Henzinger
:
Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications. SODA 2021: 1226-1245 - 2020
- [c22]Sebastian Forster
, Danupon Nanongkai, Liu Yang, Thatchaphol Saranurak
, Sorrachai Yingchareonthawornchai:
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms. SODA 2020: 2046-2065 - 2019
- [c21]Aaron Bernstein, Sebastian Forster, Monika Henzinger
:
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching. SODA 2019: 1899-1918 - [c20]Sebastian Forster
, Gramoz Goranci:
Dynamic low-stretch trees via dynamic low-diameter decompositions. STOC 2019: 377-388 - 2018
- [c19]Sebastian Forster
, Danupon Nanongkai:
A Faster Distributed Single-Source Shortest Paths Algorithm. FOCS 2018: 686-697 - 2017
- [c18]Loukas Georgiadis
, Thomas Dueholm Hansen, Giuseppe F. Italiano, Sebastian Krinninger
, Nikos Parotsidis
:
Decremental Data Structures for Connectivity and Dominators in Directed Graphs. ICALP 2017: 42:1-42:15 - [c17]Karl Bringmann, Thomas Dueholm Hansen, Sebastian Krinninger
:
Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs. ICALP 2017: 124:1-124:16 - [c16]Ittai Abraham, Shiri Chechik, Sebastian Krinninger:
Fully dynamic all-pairs shortest paths with worst-case update-time revisited. SODA 2017: 440-452 - [c15]Ruben Becker
, Andreas Karrenbauer, Sebastian Krinninger
, Christoph Lenzen:
Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. DISC 2017: 7:1-7:16 - [c14]Karl Bringmann, Sebastian Krinninger
:
Brief Announcement: A Note on Hardness of Diameter Approximation. DISC 2017: 44:1-44:3 - 2016
- [c13]Greg Bodwin, Sebastian Krinninger
:
Fully Dynamic Spanners with Worst-Case Update Time. ESA 2016: 17:1-17:18 - [c12]Ittai Abraham, David Durfee, Ioannis Koutis
, Sebastian Krinninger
, Richard Peng:
On Fully Dynamic Graph Sparsifiers. FOCS 2016: 335-344 - [c11]Monika Henzinger
, Sebastian Krinninger
, Danupon Nanongkai:
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. STOC 2016: 489-498 - 2015
- [c10]Monika Henzinger, Sebastian Krinninger
, Veronika Loitzenbauer:
Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time. ICALP (1) 2015: 713-724 - [c9]Monika Henzinger, Sebastian Krinninger
, Danupon Nanongkai:
Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs. ICALP (1) 2015: 725-736 - [c8]Monika Henzinger
, Sebastian Krinninger
, Danupon Nanongkai, Thatchaphol Saranurak
:
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture. STOC 2015: 21-30 - 2014
- [c7]Monika Henzinger
, Sebastian Krinninger
, Danupon Nanongkai:
Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time. FOCS 2014: 146-155 - [c6]Monika Henzinger
, Sebastian Krinninger, Danupon Nanongkai:
A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths. SODA 2014: 1053-1072 - [c5]Monika Henzinger
, Sebastian Krinninger
, Danupon Nanongkai:
Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. STOC 2014: 674-683 - 2013
- [c4]Monika Henzinger
, Sebastian Krinninger
, Danupon Nanongkai:
Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization. FOCS 2013: 538-547 - [c3]Monika Henzinger, Sebastian Krinninger
, Danupon Nanongkai:
Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks. ICALP (2) 2013: 607-619 - [c2]Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger, Veronika Loitzenbauer:
Approximating the minimum cycle mean. GandALF 2013: 136-149 - 2012
- [c1]Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger
, Danupon Nanongkai:
Polynomial-Time Algorithms for Energy Games with Special Weight Structures. ESA 2012: 301-312
Parts in Books or Collections
- 2015
- [p1]Sebastian Krinninger:
Schnellere Approximationsalgorithmen zur Partiell-Dynamischen Berechnung Kürzester Wege. Ausgezeichnete Informatikdissertationen 2015: 161-170
Reference Works
- 2016
- [r1]Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai:
Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrierand Derandomization. Encyclopedia of Algorithms 2016: 600-602
Informal and Other Publications
- 2023
- [i35]Sebastian Forster, Gramoz Goranci, Yasamin Nazari
, Antonis Skarlatos:
Bootstrapping Dynamic Distance Oracles. CoRR abs/2303.06102 (2023) - [i34]Sebastian Forster, Tijn de Vos:
The Laplacian Paradigm in Deterministic Congested Clique. CoRR abs/2304.02315 (2023) - [i33]Michal Dory, Sebastian Forster, Yael Kirkpatrick, Yasamin Nazari, Virginia Vassilevska Williams, Tijn de Vos:
Fast 2-Approximate All-Pairs Shortest Paths. CoRR abs/2307.09258 (2023) - [i32]Jan van den Brand, Sebastian Forster, Yasamin Nazari, Adam Polak:
On Dynamic Graph Algorithms with Predictions. CoRR abs/2307.09961 (2023) - [i31]Emilio Cruciani, Sebastian Forster, Gramoz Goranci, Yasamin Nazari, Antonis Skarlatos:
Dynamic algorithms for k-center on graphs. CoRR abs/2307.15557 (2023) - 2022
- [i30]Sebastian Forster, Tijn de Vos:
The Laplacian Paradigm in the Broadcast Congested Clique. CoRR abs/2205.12059 (2022) - [i29]Michal Dory, Sebastian Forster, Yasamin Nazari
, Tijn de Vos:
New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths. CoRR abs/2211.01152 (2022) - [i28]Sebastian Forster, Yasamin Nazari
, Maximilian Probst Gutenberg:
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch. CoRR abs/2211.04217 (2022) - [i27]Aaron Bernstein, Shiri Chechik, Sebastian Forster, Tsvi Kopelowitz, Yasamin Nazari, Nicole Wein:
Dynamic Graph Algorithms (Dagstuhl Seminar 22461). Dagstuhl Reports 12(11): 45-65 (2022) - 2021
- [i26]Jan van den Brand, Sebastian Forster, Yasamin Nazari:
Fast Deterministic Fully Dynamic Distance Approximation. CoRR abs/2111.03361 (2021) - [i25]Sebastian Forster, Martin Grösbacher, Tijn de Vos:
An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions. CoRR abs/2111.08975 (2021) - [i24]Sebastian Forster, Tijn de Vos:
Faster Cut Sparsification of Weighted Graphs. CoRR abs/2112.03120 (2021) - 2020
- [i23]Sebastian Forster, Gramoz Goranci, Monika Henzinger:
Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications. CoRR abs/2004.10319 (2020) - [i22]Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun, Mingquan Ye:
Minor Sparsifiers and the Distributed Laplacian Paradigm. CoRR abs/2012.15675 (2020) - 2019
- [i21]Sebastian Forster, Liu Yang:
A Faster Local Algorithm for Detecting Bounded-Size Cuts with Applications to Higher-Connectivity Problems. CoRR abs/1904.08382 (2019) - [i20]Sebastian Forster, Danupon Nanongkai, Thatchaphol Saranurak, Liu Yang, Sorrachai Yingchareonthawornchai:
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms. CoRR abs/1910.14344 (2019) - 2018
- [i19]Gramoz Goranci, Sebastian Krinninger:
Dynamic Low-Stretch Trees via Dynamic Low-Diameter~Decompositions. CoRR abs/1804.04928 (2018) - [i18]Aaron Bernstein, Sebastian Forster, Monika Henzinger:
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching. CoRR abs/1810.10932 (2018) - 2017
- [i17]Karl Bringmann, Thomas Dueholm Hansen, Sebastian Krinninger:
Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs. CoRR abs/1704.08122 (2017) - [i16]Loukas Georgiadis, Thomas Dueholm Hansen, Giuseppe F. Italiano, Sebastian Krinninger, Nikos Parotsidis:
Decremental Data Structures for Connectivity and Dominators in Directed Graphs. CoRR abs/1704.08235 (2017) - [i15]Karl Bringmann, Sebastian Krinninger:
A Note on Hardness of Diameter Approximation. CoRR abs/1705.02127 (2017) - [i14]Sebastian Krinninger, Danupon Nanongkai:
A Faster Distributed Single-Source Shortest Paths Algorithm. CoRR abs/1711.01364 (2017) - 2016
- [i13]Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, Richard Peng:
On Fully Dynamic Graph Sparsifiers. CoRR abs/1604.02094 (2016) - [i12]Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai:
Polynomial-Time Algorithms for Energy Games with Special Weight Structures. CoRR abs/1604.08234 (2016) - [i11]Greg Bodwin, Sebastian Krinninger:
Fully Dynamic Spanners with Worst-Case Update Time. CoRR abs/1606.07864 (2016) - [i10]Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, Christoph Lenzen:
Approximate Undirected Transshipment and Shortest Paths via Gradient Descent. CoRR abs/1607.05127 (2016) - [i9]Ittai Abraham, Shiri Chechik, Sebastian Krinninger:
Fully dynamic all-pairs shortest paths with worst-case update-time revisited. CoRR abs/1607.05132 (2016) - [i8]Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai:
Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs. CoRR abs/1612.03856 (2016) - 2015
- [i7]Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai:
An Almost-Tight Distributed Algorithm for Computing Single-Source Shortest Paths. CoRR abs/1504.07056 (2015) - [i6]Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai:
Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs. CoRR abs/1504.07959 (2015) - [i5]Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, Thatchaphol Saranurak:
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture. CoRR abs/1511.06773 (2015) - [i4]Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai:
Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks. CoRR abs/1512.08147 (2015) - [i3]Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai:
Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time. CoRR abs/1512.08148 (2015) - 2014
- [i2]Monika Henzinger, Sebastian Krinninger, Veronika Loitzenbauer:
Finding 2-edge and 2-vertex strongly connected components in quadratic time. CoRR abs/1412.6466 (2014) - 2013
- [i1]Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai:
Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization. CoRR abs/1308.0776 (2013)
Coauthor Index
![](https://dblp.dagstuhl.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-05 20:16 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint