- 2022
- Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay:
SETH-based Lower Bounds for Subset Sum and Bicriteria Path. ACM Trans. Algorithms 18(1): 6:1-6:22 (2022) - Pankaj K. Agarwal
, Ravid Cohen, Dan Halperin, Wolfgang Mulzer:
Maintaining the Union of Unit Discs under Insertions with Near-Optimal Overhead. ACM Trans. Algorithms 18(3): 26:1-26:27 (2022) - Pankaj K. Agarwal, Hsien-Chih Chang, Subhash Suri, Allen Xiao, Jie Xue:
Dynamic Geometric Set Cover and Hitting Set. ACM Trans. Algorithms 18(4): 40:1-40:37 (2022) - Rahul Arya, Sunil Arya, Guilherme Dias da Fonseca, David M. Mount:
Optimal Bound on the Combinatorial Complexity of Approximating Polytopes. ACM Trans. Algorithms 18(4): 35:1-35:29 (2022) - Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova:
Tolerant Testers of Image Properties. ACM Trans. Algorithms 18(4): 37:1-37:39 (2022) - Sayan Bhattacharya, Fabrizio Grandoni, Janardhan Kulkarni, Quanquan C. Liu, Shay Solomon:
Fully Dynamic (Δ +1)-Coloring in O(1) Update Time. ACM Trans. Algorithms 18(2): 10:1-10:25 (2022) - Thomas Bläsius, Cedric Freiberger, Tobias Friedrich, Maximilian Katzmann, Felix Montenegro-Retana, Marianne Thieffry:
Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry. ACM Trans. Algorithms 18(2): 19:1-19:32 (2022) - Antonio Boffa, Paolo Ferragina, Giorgio Vinciguerra:
A Learned Approach to Design Compressed Rank/Select Data Structures. ACM Trans. Algorithms 18(3): 24:1-24:28 (2022) - Édouard Bonnet:
4 vs 7 Sparse Undirected Unweighted Diameter Is SETH-hard at Time n4/3. ACM Trans. Algorithms 18(2): 11:1-11:14 (2022) - Sergio Cabello:
Computing the Inverse Geodesic Length in Planar Graphs and Graphs of Bounded Treewidth. ACM Trans. Algorithms 18(2): 14:1-14:26 (2022) - Nairen Cao, Jeremy T. Fineman, Katina Russell, Eugene Yang:
I/O-Efficient Algorithms for Topological Sort and Related Problems. ACM Trans. Algorithms 18(1): 5:1-5:24 (2022) - Pak Hay Chan, Lap Chi Lau, Aaron Schild, Sam Chiu-wai Wong, Hong Zhou:
Network Design for s-t Effective Resistance. ACM Trans. Algorithms 18(3): 22:1-22:45 (2022) - Hsien-Chih Chang, Arnaud de Mesmay:
Tightening Curves on Surfaces Monotonically with Applications. ACM Trans. Algorithms 18(4): 36:1-36:32 (2022) - Panagiotis Charalampopoulos, Shay Mozes, Benjamin Tebeka:
Exact Distance Oracles for Planar Graphs with Failing Vertices. ACM Trans. Algorithms 18(2): 18:1-18:23 (2022) - Xi Chen, Tim Randolph, Rocco A. Servedio, Timothy Sun:
A Lower Bound on Cycle-Finding in Sparse Digraphs. ACM Trans. Algorithms 18(4): 31:1-31:23 (2022) - Siu-Wing Cheng, Man-Kit Lau:
Dynamic Distribution-Sensitive Point Location. ACM Trans. Algorithms 18(1): 3:1-3:63 (2022) - Marek Chrobak, Mordecai J. Golin, J. Ian Munro, Neal E. Young:
A Simple Algorithm for Optimal Search Trees with Two-way Comparisons. ACM Trans. Algorithms 18(1): 2:1-2:11 (2022) - Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, Jakub Onufry Wojtaszczyk:
Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time. ACM Trans. Algorithms 18(2): 17:1-17:31 (2022) - John Fearnley, Dömötör Pálvölgyi, Rahul Savani:
A Faster Algorithm for Finding Tarski Fixed Points. ACM Trans. Algorithms 18(3): 23:1-23:23 (2022) - Weiming Feng, Heng Guo, Yitong Yin, Chihao Zhang:
Rapid Mixing from Spectral Independence beyond the Boolean Domain. ACM Trans. Algorithms 18(3): 28:1-28:32 (2022) - Alessandra Graf, David G. Harris, Penny Haxell:
Algorithms for Weighted Independent Transversals and Strong Colouring. ACM Trans. Algorithms 18(1): 1:1-1:16 (2022) - Andrzej Grzesik, Tereza Klimosová, Marcin Pilipczuk, Michal Pilipczuk:
Polynomial-time Algorithm for Maximum Weight Independent Set on P6-free Graphs. ACM Trans. Algorithms 18(1): 4:1-4:57 (2022) - Joachim Gudmundsson, Sampson Wong:
Improving the Dilation of a Metric Graph by Adding Edges. ACM Trans. Algorithms 18(3): 20:1-20:20 (2022) - John Haslegrave, Thomas Sauerwald, John Sylvester:
Time Dependent Biased Random Walks. ACM Trans. Algorithms 18(2): 12:1-12:30 (2022) - Monika Henzinger, Pan Peng:
Constant-time Dynamic (Δ +1)-Coloring. ACM Trans. Algorithms 18(2): 16:1-16:21 (2022) - Martin Hoefer, Tsvi Kopelowitz:
Introduction to the ACM-SIAM Symposium on Discrete Algorithms (SODA) 2019 Special Issue. ACM Trans. Algorithms 18(1): 4e:1-4e:2 (2022) - Zhihao Jiang, Debmalya Panigrahi, Kevin Sun:
Online Algorithms for Weighted Paging with Predictions. ACM Trans. Algorithms 18(4): 39:1-39:27 (2022) - Kai Jin, Siu-Wing Cheng, Man-Kwun Chiu, Man Ting Wong:
A Generalization of Self-Improving Algorithms. ACM Trans. Algorithms 18(3): 29:1-29:32 (2022) - Matthew Joseph, Jieming Mao, Aaron Roth:
Exponential Separations in Local Privacy. ACM Trans. Algorithms 18(4): 32:1-32:17 (2022) - Gautam Kamath, Sepehr Assadi, Anne Driemel, Janardhan Kulkarni:
Introduction to the Special Issue on ACM-SIAM Symposium on Discrete Algorithms (SODA) 2020. ACM Trans. Algorithms 18(4): 30:1-30:2 (2022)
