Liam Roditty

According to our database, Liam Roditty authored at least 87 papers between 2002 and 2025.

Collaborative distances:

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

2025

Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms.

Liam Roditty, Ariel Sapir

CoRR, September, 2025

New approximate distance oracles and their applications.

Avi Kadria, Liam Roditty

CoRR, September, 2025

Faster Algorithms for (2k-1)-Stretch Distance Oracles.

Avi Kadria, Liam Roditty

CoRR, July, 2025

New algorithms for girth and cycle detection.

Liam Roditty, Plia Trabelsi

CoRR, July, 2025

Compact Routing Schemes in Undirected and Directed Graphs.

Avi Kadria, Liam Roditty

Proceedings of the 39th International Symposium on Distributed Computing, 2025

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

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

Tsvi Kopelowitz, Ariel Korin, Liam Roditty

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

The Complexity of Manipulation of k-Coalitional Games on Graphs.

Hodaya Barr, Yohai Trabelsi, Sarit Kraus, Liam Roditty, Noam Hazon

Proceedings of the ECAI 2024 - 27th European Conference on Artificial Intelligence, 19-24 October 2024, Santiago de Compostela, Spain, 2024

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

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

Approximate Distance Oracles with Improved Stretch for Sparse Graphs.

Liam Roditty, Roei Tov

Proceedings of the Computing and Combinatorics - 27th International Conference, 2021

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

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

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

Approximate Single Source Fault Tolerant Shortest Path.

Surender Baswana, Keerti Choudhary, Moazzam Hussain, Liam Roditty

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

Stabbing Pairwise Intersecting Disks by Five Points.

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

Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

2017

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

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

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

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

Surender Baswana, Keerti Choudhary, Liam Roditty

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Distance Oracles for Sparse Graphs.

Liam Roditty

Encyclopedia of Algorithms, 2016

Approximating the Diameter.

Liam Roditty

Encyclopedia of Algorithms, 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

Routing in Unit Disk Graphs.

Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth

Proceedings of the LATIN 2016: Theoretical Informatics, 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

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

Asaf Frieder, Liam Roditty

ACM J. Exp. Algorithmics, 2014

Close to Linear Space Routing Schemes.

Liam Roditty, Roei Tov

Proceedings of the Distributed Computing - 28th International Symposium, 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

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

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

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

f-Sensitivity Distance Oracles and Routing Schemes.

Shiri Chechik, Michael Langberg, David Peleg, Liam Roditty

Algorithmica, 2012

Configurations and Minority in the String Consensus Problem.

Amihood Amir, Haim Paryenty, Liam Roditty

Proceedings of the String Processing and Information Retrieval, 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

Approximations and Partial Solutions for the Consensus Sequence Problem.

Amihood Amir, Haim Parienty, Liam Roditty

Proceedings of the String Processing and Information Retrieval, 2011

Approximating the Girth.

Liam Roditty, Roei Tov

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 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

Preprocess, Set, Query!

Ely Porat, Liam Roditty

Proceedings of the Algorithms - ESA 2011, 2011

An Experimental Study on Approximating K Shortest Simple Paths.

Asaf Frieder, Liam Roditty

Proceedings of the Algorithms - ESA 2011, 2011

2010

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

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

Relaxed Spanners for Directed Disk Graphs.

David Peleg, Liam Roditty

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

Distance Oracles beyond the Thorup-Zwick Bound.

Mihai Patrascu, Liam Roditty

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

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

Shiri Chechik, Michael Langberg, David Peleg, Liam Roditty

Proceedings of the Algorithms, 2010

2009

Fault-tolerant spanners for general graphs.

Shiri Chechik, Michael Langberg, David Peleg, Liam Roditty

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 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

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

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

Yuval Emek, David Peleg, Liam Roditty

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

All-Pairs Shortest Paths with a Sublinear Additive Error.

Liam Roditty, Asaf Shapira

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Dynamic Connectivity: Connecting to Networks and Geometry.

Timothy M. Chan, Mihai Patrascu, Liam Roditty

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

An Optimal Dynamic Spanner for Doubling Metric Spaces.

Lee-Ad Gottlieb, Liam Roditty

Proceedings of the Algorithms, 2008

Localized Spanner Construction for Ad Hoc Networks with Variable Transmission Range.

David Peleg, Liam Roditty

Proceedings of the Ad-hoc, Mobile and Wireless Networks, 7th International Conference, 2008

2007

On bounded leg shortest paths problems.

Liam Roditty, Michael Segal

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

Fully dynamic geometric spanners.

Liam Roditty

Proceedings of the 23rd ACM Symposium on Computational Geometry, 2007

2006

Dynamic and static algorithms for path problems in graphs

Liam Roditty

PhD thesis, 2006

On nash equilibria for a network creation game.

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

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

2005

Replacement Paths and <i>k</i> Simple Shortest Paths in Unweighted Directed Graphs.

Liam Roditty, Uri Zwick

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 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

2004

A fully dynamic reachability algorithm for directed graphs with an almost linear update time.

Liam Roditty, Uri Zwick

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs.

Liam Roditty, Uri Zwick

Proceedings of the 45th Symposium on Foundations of Computer Science, 2004

On Dynamic Shortest Paths Problems.

Liam Roditty, Uri Zwick

Proceedings of the Algorithms, 2004

2003

A faster and simpler fully dynamic transitive closure.

Liam Roditty

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

2002

Roundtrip spanners and roundtrip routing in directed graphs.

Liam Roditty, Mikkel Thorup, Uri Zwick

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Improved Dynamic Reachability Algorithms for Directed Graphs.

Liam Roditty, Uri Zwick

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002