Christian Wulff-Nilsen

Panagiotis Charalampopoulos

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

2023

Almost Optimal Exact Distance Oracles for Planar Graphs.

[BibT_eX]

[DOI]

J. ACM, April, 2023

Fully Dynamic Exact Edge Connectivity in Sublinear Time.

[BibT_eX]

[DOI]

Gramoz Goranci

Monika Henzinger

Thatchaphol Saranurak

Mikkel Thorup

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

2022

Special Section on the Fifty-Second Annual ACM Symposium on the Theory of Computing (STOC 2020).

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

Marek Cygan

Noga Ron-Zewi

SIAM J. Comput., June, 2022

Constructing light spanners deterministically in near-linear time.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2022

Negative-Weight Single-Source Shortest Paths in Almost-linear Time.

[BibT_eX]

[DOI]

CoRR, 2022

A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs.

[BibT_eX]

[DOI]

Debarati Das

Evangelos Kipouridis

Proceedings of the 5th Symposium on Simplicity in Algorithms, 2022

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs.

[BibT_eX]

[DOI]

Debarati Das

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

Negative-Weight Single-Source Shortest Paths in Near-linear Time.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Algorithms and Computation, 2021

Near-Optimal Distance Oracles for Vertex-Labeled Planar Graphs.

[BibT_eX]

[DOI]

Jacob Evald

Proceedings of the 32nd International Symposium on Algorithms and Computation, 2021

Decremental APSP in Unweighted Digraphs Versus an Adaptive Adversary.

[BibT_eX]

[DOI]

Jacob Evald

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Optimal Approximate Distance Oracle for Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Escaping an Infinitude of Lions.

[BibT_eX]

[DOI]

Mikkel Abrahamsen

Jacob Holm

Eva Rotenberg

Am. Math. Mon., 2020

Decremental APSP in Directed Graphs Versus an Adaptive Adversary.

[BibT_eX]

[DOI]

Jacob Evald

CoRR, 2020

Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds.

[BibT_eX]

[DOI]

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

Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary.

[BibT_eX]

[DOI]

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

Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler.

[BibT_eX]

[DOI]

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

Near-Optimal Decremental SSSP in Dense Weighted Digraphs.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Decremental strongly-connected components and single-source reachability in near-linear time.

[BibT_eX]

[DOI]

Maximilian Probst

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Greedy spanners are optimal in doubling metrics.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

Near-Optimal Light Spanners.

[BibT_eX]

[DOI]

Shiri Chechik

ACM Trans. Algorithms, 2018

Better Tradeoffs for Exact Distance Oracles in Planar Graphs.

[BibT_eX]

[DOI]

Pawel Gawrychowski

Oren Weimann

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

2017

Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

Fully-dynamic minimum spanning forest with improved worst-case update time.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time.

[BibT_eX]

[DOI]

Thatchaphol Saranurak

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Fast and Compact Exact Distance Oracle for Planar Graphs.

[BibT_eX]

[DOI]

Vincent Cohen-Addad

Søren Dahlgaard

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Minor-Free Graphs Have Light Spanners.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Best Laid Plans of Lions and Men.

[BibT_eX]

[DOI]

Mikkel Abrahamsen

Jacob Holm

Eva Rotenberg

Proceedings of the 33rd International Symposium on Computational Geometry, 2017

2016

Faster Deterministic Fully-Dynamic Graph Connectivity.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Approximate Distance Oracles with Improved Query Time.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Space-efficient path-reporting approximate distance oracles.

[BibT_eX]

[DOI]

Michael Elkin

Ofer Neiman

Theor. Comput. Sci., 2016

Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Brief Announcement: Labeling Schemes for Power-Law Graphs.

[BibT_eX]

[DOI]

Casper Petersen

Noy Rotbart

Jakob Grue Simonsen

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

Near Optimal Adjacency Labeling Schemes for Power-Law Graphs.

[BibT_eX]

[DOI]

Casper Petersen

Noy Rotbart

Jakob Grue Simonsen

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs.

[BibT_eX]

[DOI]

David Eppstein

Amir Nayyeri

Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015

Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2015

Near-optimal adjacency labeling scheme for power-law graphs.

[BibT_eX]

[DOI]

Casper Petersen

Noy Rotbart

Jakob Grue Simonsen

CoRR, 2015

Faster Fully-Dynamic Minimum Spanning Forest.

[BibT_eX]

[DOI]

Jacob Holm

Eva Rotenberg

Proceedings of the Algorithms - ESA 2015, 2015

2014

Faster Separators for Shallow Minor-Free Graphs via Dynamic Approximate Distance Oracles.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time.

[BibT_eX]

[DOI]

Comput. Geom., 2013

Faster Deterministic Fully-Dynamic Graph Connectivity.

[BibT_eX]

[DOI]

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

Approximate Distance Oracles with Improved Query Time.

[BibT_eX]

[DOI]

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

2012

Computing the Stretch factor and Maximum Detour of Paths, Trees, and cycles in the normed Space.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 2012

Connectivity Oracles for Planar Graphs.

[BibT_eX]

[DOI]

Seth Pettie

Proceedings of the Algorithm Theory - SWAT 2012, 2012

Approximate distance oracles with improved preprocessing time.

[BibT_eX]

[DOI]

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

Single Source - All Sinks Max Flows in Planar Digraphs.

[BibT_eX]

[DOI]

Jakub Lacki

Yahav Nussbaum

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

2011

Improved algorithms for min cut and max flow in undirected planar graphs.

[BibT_eX]

[DOI]

Giuseppe F. Italiano

Yahav Nussbaum

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications.

[BibT_eX]

[DOI]

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

2010

Bounding the expected number of rectilinear full Steiner trees.

[BibT_eX]

[DOI]

Networks, 2010

Computing the Maximum Detour of a Plane Geometric Graph in Subquadratic Time.

[BibT_eX]

[DOI]

J. Comput. Geom., 2010

Multiple source, single sink maximum flow in a planar graph

[BibT_eX]

[DOI]

CoRR, 2010

Faster Shortest Path Algorithm for H-Minor Free Graphs with Negative Edge Weights

[BibT_eX]

[DOI]

CoRR, 2010

Min st-Cut of a Planar Graph in O(n loglog n) Time

[BibT_eX]

[DOI]

CoRR, 2010

Computing the dilation of edge-augmented graphs in metric spaces.

[BibT_eX]

[DOI]

Comput. Geom., 2010

Solving the Replacement Paths Problem for Planar Directed Graphs in O(n log n) Time.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Min st-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time.

[BibT_eX]

[DOI]

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

Shortest Paths in Planar Graphs with Real Lengths in O(nlog2n/loglogn) Time.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2010

2009

A novel approach to phylogenetic trees: d-Dimensional geometric Steiner trees.

[BibT_eX]

[DOI]

Martin Zachariasen

Networks, 2009

Minimum Cycle Basis and All-Pairs Min Cut of a Planar Graph in Subquadratic Time

[BibT_eX]

[DOI]

CoRR, 2009

Shortest Paths in Planar Graphs with Real Lengths in $O(n\log^2n/\log\log n)$ Time

[BibT_eX]

[DOI]

CoRR, 2009

Girth of a Planar Digraph with Real Edge Weights in O(n(log n)^3) Time

[BibT_eX]

[DOI]

CoRR, 2009

2008

Steiner hull algorithm for the uniform orientation metrics.

[BibT_eX]

[DOI]

Comput. Geom., 2008

Computing the Maximum Detour of a Plane Graph in Subquadratic Time.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces.

[BibT_eX]

[DOI]

Jun Luo

Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

Computing the Stretch Factor of Paths, Trees, and Cycles in Weighted Fixed Orientation Metrics.

[BibT_eX]