Please note that ISTA Research Explorer no longer supports Internet Explorer versions 8 or 9 (or earlier).
We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox.
26 Publications
2023 |Published| Journal Article | IST-REx-ID: 12563 |
![Open access file OA](https://research-explorer.ista.ac.at/images/access_open.png)
Topology and adjunction in promise constraint satisfaction
A. Krokhin, J. Opršal, M. Wrochna, S. Živný, SIAM Journal on Computing 52 (2023) 38–79.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| WoS
| arXiv
A. Krokhin, J. Opršal, M. Wrochna, S. Živný, SIAM Journal on Computing 52 (2023) 38–79.
2023 |Published| Journal Article | IST-REx-ID: 12960 |
![Open access file OA](https://research-explorer.ista.ac.at/images/access_open.png)
Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations
J.D. Boissonnat, S. Kachanovich, M. Wintraecken, SIAM Journal on Computing 52 (2023) 452–486.
[Submitted Version]
View
| Files available
| DOI
| Download Submitted Version (ext.)
| WoS
J.D. Boissonnat, S. Kachanovich, M. Wintraecken, SIAM Journal on Computing 52 (2023) 452–486.
2023 |Published| Journal Article | IST-REx-ID: 14558
Deterministic near-optimal approximation algorithms for dynamic set cover
S. Bhattacharya, M.H. Henzinger, D. Nanongkai, X. Wu, SIAM Journal on Computing 52 (2023) 1132–1192.
View
| DOI
S. Bhattacharya, M.H. Henzinger, D. Nanongkai, X. Wu, SIAM Journal on Computing 52 (2023) 1132–1192.
2023 |Published| Journal Article | IST-REx-ID: 14364 |
![Open access file OA](https://research-explorer.ista.ac.at/images/access_open.png)
Why extension-based proofs fail
D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, L. Zhu, SIAM Journal on Computing 52 (2023) 913–944.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| WoS
| arXiv
D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, L. Zhu, SIAM Journal on Computing 52 (2023) 913–944.
2021 |Published| Journal Article | IST-REx-ID: 11886 |
![Open access file OA](https://research-explorer.ista.ac.at/images/access_open.png)
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
M.H. Henzinger, S. Krinninger, D. Nanongkai, SIAM Journal on Computing 50 (2021) STOC16-98-STOC16-137.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
M.H. Henzinger, S. Krinninger, D. Nanongkai, SIAM Journal on Computing 50 (2021) STOC16-98-STOC16-137.
2021 |Published| Journal Article | IST-REx-ID: 15271
Simple, deterministic, constant-round coloring in congested clique and MPC
A. Czumaj, P. Davies, M. Parter, SIAM Journal on Computing 50 (2021) 1603–1626.
View
| DOI
A. Czumaj, P. Davies, M. Parter, SIAM Journal on Computing 50 (2021) 1603–1626.
2020 |Published| Journal Article | IST-REx-ID: 11889
Local flow partitioning for faster edge connectivity
M.H. Henzinger, S. Rao, D. Wang, SIAM Journal on Computing 49 (2020) 1–36.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
M.H. Henzinger, S. Rao, D. Wang, SIAM Journal on Computing 49 (2020) 1–36.
2019 |Published| Journal Article | IST-REx-ID: 6672 |
![Open access file OA](https://research-explorer.ista.ac.at/images/access_open.png)
Anisotropic triangulations via discrete Riemannian Voronoi diagrams
J.-D. Boissonnat, M. Rouxel-Labbé, M. Wintraecken, SIAM Journal on Computing 48 (2019) 1046–1097.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
J.-D. Boissonnat, M. Rouxel-Labbé, M. Wintraecken, SIAM Journal on Computing 48 (2019) 1046–1097.
2019 |Published| Journal Article | IST-REx-ID: 7412 |
![Open access file OA](https://research-explorer.ista.ac.at/images/access_open.png)
A local lemma for focused stochastical algorithms
D. Achlioptas, F. Iliopoulos, V. Kolmogorov, SIAM Journal on Computing 48 (2019) 1583–1602.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| WoS
| arXiv
D. Achlioptas, F. Iliopoulos, V. Kolmogorov, SIAM Journal on Computing 48 (2019) 1583–1602.
2018 |Published| Journal Article | IST-REx-ID: 11890 |
![Open access file OA](https://research-explorer.ista.ac.at/images/access_open.png)
Deterministic fully dynamic data structures for vertex cover and matching
S. Bhattacharya, M.H. Henzinger, G.F. Italiano, SIAM Journal on Computing 47 (2018) 859–887.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
S. Bhattacharya, M.H. Henzinger, G.F. Italiano, SIAM Journal on Computing 47 (2018) 859–887.
2018 |Published| Journal Article | IST-REx-ID: 5975 |
![Open access file OA](https://research-explorer.ista.ac.at/images/access_open.png)
Commutativity in the algorithmic Lovász local lemma
V. Kolmogorov, SIAM Journal on Computing 47 (2018) 2029–2056.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| WoS
| arXiv
V. Kolmogorov, SIAM Journal on Computing 47 (2018) 2029–2056.
2016 |Published| Journal Article | IST-REx-ID: 11891 |
![Open access file OA](https://research-explorer.ista.ac.at/images/access_open.png)
Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization
M.H. Henzinger, S. Krinninger, D. Nanongkai, SIAM Journal on Computing 45 (2016) 947–1006.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
M.H. Henzinger, S. Krinninger, D. Nanongkai, SIAM Journal on Computing 45 (2016) 947–1006.
2001 |Published| Journal Article | IST-REx-ID: 11892
Maintaining minimum spanning forests in dynamic graphs
M.H. Henzinger, V. King, SIAM Journal on Computing 31 (2001) 364–374.
View
| DOI
M.H. Henzinger, V. King, SIAM Journal on Computing 31 (2001) 364–374.
2000 |Published| Journal Article | IST-REx-ID: 11694
Exploring unknown environments
S. Albers, M.H. Henzinger, SIAM Journal on Computing 29 (2000) 1164–1188.
View
| DOI
S. Albers, M.H. Henzinger, SIAM Journal on Computing 29 (2000) 1164–1188.
2000 |Published| Journal Article | IST-REx-ID: 11893
Improved data structures for fully dynamic biconnectivity
M.H. Henzinger, SIAM Journal on Computing 29 (2000) 1761–1815.
View
| DOI
M.H. Henzinger, SIAM Journal on Computing 29 (2000) 1761–1815.
1994 |Published| Journal Article | IST-REx-ID: 4033
Selecting heavily covered points
B. Chazelle, H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, SIAM Journal on Computing 23 (1994) 1138–1151.
View
| DOI
| Download None (ext.)
B. Chazelle, H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, SIAM Journal on Computing 23 (1994) 1138–1151.
1993 |Published| Journal Article | IST-REx-ID: 4041
On the zone theorem for hyperplane arrangements
H. Edelsbrunner, R. Seidel, M. Sharir, SIAM Journal on Computing 22 (1993) 418–429.
View
| DOI
| Download None (ext.)
H. Edelsbrunner, R. Seidel, M. Sharir, SIAM Journal on Computing 22 (1993) 418–429.
1993 |Published| Journal Article | IST-REx-ID: 4036
Computing a face in an arrangement of line segments and related problems
B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, J. Snoeyink, SIAM Journal on Computing 22 (1993) 1286–1302.
View
| DOI
| Download None (ext.)
B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, J. Snoeyink, SIAM Journal on Computing 22 (1993) 1286–1302.
1993 |Published| Journal Article | IST-REx-ID: 4042
A quadratic time algorithm for the minmax length triangulation
H. Edelsbrunner, T. Tan, SIAM Journal on Computing 22 (1993) 527–551.
View
| DOI
| Download None (ext.)
H. Edelsbrunner, T. Tan, SIAM Journal on Computing 22 (1993) 527–551.
1992 |Published| Journal Article | IST-REx-ID: 4043
An O(n^2 log n) time algorithm for the MinMax angle triangulation
H. Edelsbrunner, T. Tan, R. Waupotitsch, SIAM Journal on Scientific Computing 13 (1992) 994–1008.
View
| DOI
| Download None (ext.)
H. Edelsbrunner, T. Tan, R. Waupotitsch, SIAM Journal on Scientific Computing 13 (1992) 994–1008.