Liam Roditty

According to our database, Liam Roditty authored at least 81 papers between 2005 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Dynamic Connectivity in Disk Graphs.

Alexander Baumann, Haim Kaplan, Katharina Klost, Kristin Knorr, Wolfgang Mulzer, Liam Roditty, Paul Seiferth

Discret. Comput. Geom., January, 2024

Insertion-Only Dynamic Connectivity in General Disk Graphs.

Haim Kaplan, Katharina Klost, Kristin Knorr, Wolfgang Mulzer, Liam Roditty

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

2023

Approximate distance oracles with improved stretch for sparse graphs.

Liam Roditty, Roei Tov

Theor. Comput. Sci., 2023

On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch.

Tsvi Kopelowitz, Ariel Korin, Liam Roditty

CoRR, 2023

New Algorithms for All Pairs Approximate Shortest Paths.

Liam Roditty

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Improved girth approximation in weighted undirected graphs.

Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

2022

Algorithmic trade-offs for girth approximation in undirected graphs.

Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Dynamic Connectivity in Disk Graphs.

Haim Kaplan, Alexander Kauer, Katharina Klost, Kristin Knorr, Wolfgang Mulzer, Liam Roditty, Paul Seiferth

Proceedings of the 38th International Symposium on Computational Geometry, 2022

2021

Toward Tight Approximation Bounds for Graph Diameter and Eccentricities.

Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, Nicole Wein

SIAM J. Comput., 2021

Stabbing pairwise intersecting disks by five points.

Sariel Har-Peled, Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir, Max Willert

Discret. Math., 2021

A Unified Approach for All Pairs Approximate Shortest Paths in Weighted Undirected Graphs.

Maor Akav, Liam Roditty

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

2020

Approximate Single-Source Fault Tolerant Shortest Path.

Surender Baswana, Keerti Choudhary, Moazzam Hussain, Liam Roditty

ACM Trans. Algorithms, 2020

Dynamic Planar Voronoi Diagrams for General Distance Functions and Their Algorithmic Applications.

Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir

Discret. Comput. Geom., 2020

Reachability Oracles for Directed Transmission Graphs.

Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth

Algorithmica, 2020

An almost 2-approximation for all-pairs of shortest paths in subquadratic time.

Maor Akav, Liam Roditty

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019

{-1, 0, 1}-APSP and (min, max)-Product Problems.

Hodaya Barr, Tsvi Kopelowitz, Ely Porat, Liam Roditty

CoRR, 2019

An Efficient Strongly Connected Components Algorithm in the Fault Tolerant Model.

Surender Baswana, Keerti Choudhary, Liam Roditty

Algorithmica, 2019

Algorithms and Hardness for Diameter in Dynamic Graphs.

Bertie Ancona, Monika Henzinger, Liam Roditty, Virginia Vassilevska Williams, Nicole Wein

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Triangles and Girth in Disk Graphs and Transmission Graphs.

Haim Kaplan, Katharina Klost, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018

Spanners for Directed Transmission Graphs.

Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth

SIAM J. Comput., 2018

Fault-Tolerant Subgraph for Single-Source Reachability: General and Optimal.

Surender Baswana, Keerti Choudhary, Liam Roditty

SIAM J. Comput., 2018

Routing in Unit Disk Graphs.

Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth

Algorithmica, 2018

Towards tight approximation bounds for graph diameter and eccentricities.

Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, Nicole Wein

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners.

Jakub Pachocki, Liam Roditty, Aaron Sidford, Roei Tov, Virginia Vassilevska Williams

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2016

Distance Oracles for Sparse Graphs.

Liam Roditty

Encyclopedia of Algorithms, 2016

Approximating the Diameter.

Liam Roditty

Encyclopedia of Algorithms, 2016

A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time.

Liam Roditty, Uri Zwick

SIAM J. Comput., 2016

Close to linear space routing schemes.

Liam Roditty, Roei Tov

Distributed Comput., 2016

Configurations and Minority in the String Consensus Problem.

Amihood Amir, Haim Paryenty, Liam Roditty

Algorithmica, 2016

Fault tolerant subgraph for single source reachability: generic and optimal.

Surender Baswana, Keerti Choudhary, Liam Roditty

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015

Fault Tolerant Reachability for Directed Graphs.

Surender Baswana, Keerti Choudhary, Liam Roditty

Proceedings of the Distributed Computing - 29th International Symposium, 2015

New Routing Techniques and their Applications.

Liam Roditty, Roei Tov

Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

Spanners and Reachability Oracles for Directed Transmission Graphs.

Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth

Proceedings of the 31st International Symposium on Computational Geometry, 2015

2014

On Nash Equilibria for a Network Creation Game.

Susanne Albers, Stefan Eilts, Eyal Even-Dar, Yishay Mansour, Liam Roditty

ACM Trans. Economics and Comput., 2014

Distance Oracles beyond the Thorup-Zwick Bound.

Mihai Patrascu, Liam Roditty

SIAM J. Comput., 2014

An Experimental Study on Approximating <i>k</i> Shortest Simple Paths.

Asaf Frieder, Liam Roditty

ACM J. Exp. Algorithmics, 2014

Distributed 3/2-Approximation of the Diameter.

Stephan Holzer, David Peleg, Liam Roditty, Roger Wattenhofer

Proceedings of the Distributed Computing - 28th International Symposium, 2014

Better Approximation Algorithms for the Graph Diameter.

Shiri Chechik, Daniel H. Larkin, Liam Roditty, Grant Schoenebeck, Robert Endre Tarjan, Virginia Vassilevska Williams

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Multiply Balanced k -Partitioning.

Amihood Amir, Jessica Ficler, Robert Krauthgamer, Liam Roditty, Oren Sar Shalom

Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

On the Efficiency of the Hamming C-Centerstring Problems.

Amihood Amir, Jessica Ficler, Liam Roditty, Oren Sar Shalom

Proceedings of the Combinatorial Pattern Matching - 25th Annual Symposium, 2014

2013

Approximating the Girth.

Liam Roditty, Roei Tov

ACM Trans. Algorithms, 2013

On the hardness of the Consensus String problem.

Amihood Amir, Haim Paryenty, Liam Roditty

Inf. Process. Lett., 2013

A Labeling Approach to Incremental Cycle Detection.

Edith Cohen, Amos Fiat, Haim Kaplan, Liam Roditty

CoRR, 2013

Preprocess, Set, Query!

Ely Porat, Liam Roditty

Algorithmica, 2013

Relaxed Spanners for Directed Disk Graphs.

David Peleg, Liam Roditty

Algorithmica, 2013

Finding the Minimum-Weight k-Path.

Avinatan Hassidim, Orgad Keller, Moshe Lewenstein, Liam Roditty

Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013

Fast approximation algorithms for the diameter and radius of sparse graphs.

Liam Roditty, Virginia Vassilevska Williams

Proceedings of the Symposium on Theory of Computing Conference, 2013

Decremental maintenance of strongly connected components.

Liam Roditty

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012

Replacement paths and <i>k</i> simple shortest paths in unweighted directed graphs.

Liam Roditty, Uri Zwick

ACM Trans. Algorithms, 2012

Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs.

Liam Roditty, Uri Zwick

SIAM J. Comput., 2012

SINR Diagrams: Convexity and Its Applications in Wireless Networks.

Chen Avin, Yuval Emek, Erez Kantor, Zvi Lotker, David Peleg, Liam Roditty

J. ACM, 2012

Approximating the diameter of a graph

Liam Roditty, Virginia Vassilevska Williams

CoRR, 2012

Fully Dynamic Geometric Spanners.

Liam Roditty

Algorithmica, 2012

f-Sensitivity Distance Oracles and Routing Schemes.

Shiri Chechik, Michael Langberg, David Peleg, Liam Roditty

Algorithmica, 2012

Subquadratic time approximation algorithms for the girth.

Liam Roditty, Virginia Vassilevska Williams

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Distributed Algorithms for Network Diameter and Girth.

David Peleg, Liam Roditty, Elad Tal

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

A New Infinity of Distance Oracles for Sparse Graphs.

Mihai Patrascu, Liam Roditty, Mikkel Thorup

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

All-pairs shortest paths with a sublinear additive error.

Liam Roditty, Asaf Shapira

ACM Trans. Algorithms, 2011

Dynamic Connectivity: Connecting to Networks and Geometry.

Timothy M. Chan, Mihai Patrascu, Liam Roditty

SIAM J. Comput., 2011

On Dynamic Shortest Paths Problems.

Liam Roditty, Uri Zwick

Algorithmica, 2011

On Bounded Leg Shortest Paths Problems.

Liam Roditty, Michael Segal

Algorithmica, 2011

Approximations and Partial Solutions for the Consensus Sequence Problem.

Amihood Amir, Haim Parienty, Liam Roditty

Proceedings of the String Processing and Information Retrieval, 2011

Improved Dynamic Algorithms for Maintaining Approximate Shortest Paths Under Deletions.

Aaron Bernstein, Liam Roditty

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Fast, precise and dynamic distance queries.

Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz, Moshe Lewenstein, Liam Roditty

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Minimum Weight Cycles and Triangles: Equivalences and Algorithms.

Liam Roditty, Virginia Vassilevska Williams

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

An Experimental Study on Approximating K Shortest Simple Paths.

Asaf Frieder, Liam Roditty

Proceedings of the Algorithms - ESA 2011, 2011

2010

Localized spanner construction for ad hoc networks with variable transmission range.

David Peleg, Liam Roditty

ACM Trans. Sens. Networks, 2010

A near-linear-time algorithm for computing replacement paths in planar directed graphs.

Yuval Emek, David Peleg, Liam Roditty

ACM Trans. Algorithms, 2010

On the k Shortest Simple Paths Problem in Weighted Directed Graphs.

Liam Roditty

SIAM J. Comput., 2010

Fault Tolerant Spanners for General Graphs.

Shiri Chechik, Michael Langberg, David Peleg, Liam Roditty

SIAM J. Comput., 2010

Realtime Classification for Encrypted Traffic.

Roni Bar-Yanai, Michael Langberg, David Peleg, Liam Roditty

Proceedings of the Experimental Algorithms, 9th International Symposium, 2010

<i>f</i>-Sensitivity Distance Oracles and Routing Schemes.

Shiri Chechik, Michael Langberg, David Peleg, Liam Roditty

Proceedings of the Algorithms, 2010

2009

SINR diagrams: towards algorithmically usable SINR models of wireless networks.

Chen Avin, Yuval Emek, Erez Kantor, Zvi Lotker, David Peleg, Liam Roditty

Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, 2009

2008

Roundtrip spanners and roundtrip routing in directed graphs.

Liam Roditty, Mikkel Thorup, Uri Zwick

ACM Trans. Algorithms, 2008

A faster and simpler fully dynamic transitive closure.

Liam Roditty

ACM Trans. Algorithms, 2008

Improved Dynamic Reachability Algorithms for Directed Graphs.

Liam Roditty, Uri Zwick

SIAM J. Comput., 2008

Improved algorithms for fully dynamic geometric spanners and geometric routing.

Lee-Ad Gottlieb, Liam Roditty

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

An Optimal Dynamic Spanner for Doubling Metric Spaces.

Lee-Ad Gottlieb, Liam Roditty

Proceedings of the Algorithms, 2008

2007

On the <i>K</i>-simple shortest paths problem in weighted directed graphs.

Liam Roditty

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006

Dynamic and static algorithms for path problems in graphs

Liam Roditty

PhD thesis, 2006

2005

Deterministic Constructions of Approximate Distance Oracles and Spanners.

Liam Roditty, Mikkel Thorup, Uri Zwick

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005