2025
Compact routing schemes in undirected and directed graphs.
CoRR, March, 2025
2024
Dynamic Connectivity in Disk Graphs.
Discret. Comput. Geom., January, 2024
Insertion-Only Dynamic Connectivity in General Disk Graphs.
Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024
On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch.
Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024
The Complexity of Manipulation of k-Coalitional Games on Graphs.
Proceedings of the ECAI 2024 - 27th European Conference on Artificial Intelligence, 19-24 October 2024, Santiago de Compostela, Spain, 2024
2023
Approximate distance oracles with improved stretch for sparse graphs.
Theor. Comput. Sci., 2023
New Algorithms for All Pairs Approximate Shortest Paths.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023
Improved girth approximation in weighted undirected graphs.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023
2022
Algorithmic trade-offs for girth approximation in undirected graphs.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022
Dynamic Connectivity in Disk Graphs.
Proceedings of the 38th International Symposium on Computational Geometry, 2022
2021
Toward Tight Approximation Bounds for Graph Diameter and Eccentricities.
SIAM J. Comput., 2021
Stabbing pairwise intersecting disks by five points.
Discret. Math., 2021
A Unified Approach for All Pairs Approximate Shortest Paths in Weighted Undirected Graphs.
Proceedings of the 29th Annual European Symposium on Algorithms, 2021
2020
Approximate Single-Source Fault Tolerant Shortest Path.
ACM Trans. Algorithms, 2020
Dynamic Planar Voronoi Diagrams for General Distance Functions and Their Algorithmic Applications.
Discret. Comput. Geom., 2020
Reachability Oracles for Directed Transmission Graphs.
Algorithmica, 2020
An almost 2-approximation for all-pairs of shortest paths in subquadratic time.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020
2019
{-1, 0, 1}-APSP and (min, max)-Product Problems.
CoRR, 2019
An Efficient Strongly Connected Components Algorithm in the Fault Tolerant Model.
Algorithmica, 2019
Algorithms and Hardness for Diameter in Dynamic Graphs.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019
Triangles and Girth in Disk Graphs and Transmission Graphs.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019
2018
Spanners for Directed Transmission Graphs.
SIAM J. Comput., 2018
Fault-Tolerant Subgraph for Single-Source Reachability: General and Optimal.
SIAM J. Comput., 2018
Routing in Unit Disk Graphs.
Algorithmica, 2018
Towards tight approximation bounds for graph diameter and eccentricities.
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.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018
2016
Distance Oracles for Sparse Graphs.
Encyclopedia of Algorithms, 2016
Approximating the Diameter.
Encyclopedia of Algorithms, 2016
A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time.
SIAM J. Comput., 2016
Close to linear space routing schemes.
Distributed Comput., 2016
Configurations and Minority in the String Consensus Problem.
Algorithmica, 2016
Fault tolerant subgraph for single source reachability: generic and optimal.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016
2015
Fault Tolerant Reachability for Directed Graphs.
Proceedings of the Distributed Computing - 29th International Symposium, 2015
New Routing Techniques and their Applications.
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015
Spanners and Reachability Oracles for Directed Transmission Graphs.
Proceedings of the 31st International Symposium on Computational Geometry, 2015
2014
On Nash Equilibria for a Network Creation Game.
ACM Trans. Economics and Comput., 2014
Distance Oracles beyond the Thorup-Zwick Bound.
SIAM J. Comput., 2014
An Experimental Study on Approximating <i>k</i> Shortest Simple Paths.
ACM J. Exp. Algorithmics, 2014
Distributed 3/2-Approximation of the Diameter.
Proceedings of the Distributed Computing - 28th International Symposium, 2014
Better Approximation Algorithms for the Graph Diameter.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014
Multiply Balanced k -Partitioning.
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.
Proceedings of the Combinatorial Pattern Matching - 25th Annual Symposium, 2014
2013
ACM Trans. Algorithms, 2013
On the hardness of the Consensus String problem.
Inf. Process. Lett., 2013
A Labeling Approach to Incremental Cycle Detection.
CoRR, 2013
Relaxed Spanners for Directed Disk Graphs.
Algorithmica, 2013
Finding the Minimum-Weight k-Path.
Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013
Fast approximation algorithms for the diameter and radius of sparse graphs.
Proceedings of the Symposium on Theory of Computing Conference, 2013
Decremental maintenance of strongly connected components.
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.
ACM Trans. Algorithms, 2012
Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs.
SIAM J. Comput., 2012
SINR Diagrams: Convexity and Its Applications in Wireless Networks.
J. ACM, 2012
Approximating the diameter of a graph
CoRR, 2012
Fully Dynamic Geometric Spanners.
Algorithmica, 2012
f-Sensitivity Distance Oracles and Routing Schemes.
Algorithmica, 2012
Subquadratic time approximation algorithms for the girth.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012
Distributed Algorithms for Network Diameter and Girth.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012
A New Infinity of Distance Oracles for Sparse Graphs.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012
2011
All-pairs shortest paths with a sublinear additive error.
ACM Trans. Algorithms, 2011
Dynamic Connectivity: Connecting to Networks and Geometry.
SIAM J. Comput., 2011
On Dynamic Shortest Paths Problems.
Algorithmica, 2011
On Bounded Leg Shortest Paths Problems.
Algorithmica, 2011
Approximations and Partial Solutions for the Consensus Sequence Problem.
Proceedings of the String Processing and Information Retrieval, 2011
Improved Dynamic Algorithms for Maintaining Approximate Shortest Paths Under Deletions.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011
Fast, precise and dynamic distance queries.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011
Minimum Weight Cycles and Triangles: Equivalences and Algorithms.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011
An Experimental Study on Approximating K Shortest Simple Paths.
Proceedings of the Algorithms - ESA 2011, 2011
2010
Localized spanner construction for ad hoc networks with variable transmission range.
ACM Trans. Sens. Networks, 2010
A near-linear-time algorithm for computing replacement paths in planar directed graphs.
ACM Trans. Algorithms, 2010
On the k Shortest Simple Paths Problem in Weighted Directed Graphs.
SIAM J. Comput., 2010
Fault Tolerant Spanners for General Graphs.
SIAM J. Comput., 2010
Realtime Classification for Encrypted Traffic.
Proceedings of the Experimental Algorithms, 9th International Symposium, 2010
<i>f</i>-Sensitivity Distance Oracles and Routing Schemes.
Proceedings of the Algorithms, 2010
2009
SINR diagrams: towards algorithmically usable SINR models of wireless networks.
Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, 2009
2008
Roundtrip spanners and roundtrip routing in directed graphs.
ACM Trans. Algorithms, 2008
A faster and simpler fully dynamic transitive closure.
ACM Trans. Algorithms, 2008
Improved Dynamic Reachability Algorithms for Directed Graphs.
SIAM J. Comput., 2008
Improved algorithms for fully dynamic geometric spanners and geometric routing.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008
An Optimal Dynamic Spanner for Doubling Metric Spaces.
Proceedings of the Algorithms, 2008
2007
On the <i>K</i>-simple shortest paths problem in weighted directed graphs.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007
2006
Dynamic and static algorithms for path problems in graphs
PhD thesis, 2006
2005
Deterministic Constructions of Approximate Distance Oracles and Spanners.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005