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

Christian Wulff‐Nilsen

Type: Preprint

Publication Date: 2015-12-21

Citations: 15

DOI: https://doi.org/10.1137/1.9781611974331.ch26

Locations

arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff	2016	Christian Wulff-Nilsen
+	Optimal Approximate Distance Oracle for Planar Graphs	2021	Hung Le Christian Wulff‐Nilsen
+ PDF Chat	Optimal Approximate Distance Oracle for Planar Graphs	2022	Hung Le Christian Wulff‐Nilsen
+	Approximate Distance Oracles for Planar Graphs with Subpolynomial Error Dependency	2022	Hung T. Le
+ PDF Chat	Fast and Compact Exact Distance Oracle for Planar Graphs	2017	Vincent Cohen-Addad Søren Dahlgaard Christian Wulff‐Nilsen
+ PDF Chat	Approximate Distance Oracles for Planar Graphs with Subpolynomial Error Dependency	2023	Hung Le
+	Fast and Compact Exact Distance Oracle for Planar Graphs	2017	Vincent Cohen-Addad Søren Dahlgaard Christian Wulff-Nilsen
+	Fast and Compact Exact Distance Oracle for Planar Graphs	2017	Vincent Cohen-Addad Søren Dahlgaard Christian Wulff‐Nilsen
+ PDF Chat	Almost optimal distance oracles for planar graphs	2019	Panagiotis Charalampopoulos Paweł Gawrychowski Shay Mozes Oren Weimann
+	Almost Optimal Distance Oracles for Planar Graphs	2018	Panagiotis Charalampopoulos Paweł Gawrychowski Shay Mozes Oren Weimann
+	More Compact Oracles for Approximate Distances in Planar Graphs	2011	Christian Sommer
+ PDF Chat	Constant Query Time $$(1+\epsilon )$$ -Approximate Distance Oracle for Planar Graphs	2015	Qian‐Ping Gu Gengchun Xu
+	Constant Query Time $(1 + ε)$-Approximate Distance Oracle for Planar Graphs	2017	Qian‐Ping Gu Gengchun Xu
+	Approximate Distance Oracle with Constant Query Time	2013	Shiri Chechik
+ PDF Chat	Exact Distance Oracles for Planar Graphs with Failing Vertices	2022	Panagiotis Charalampopoulos Shay Mozes Benjamin Tebeka
+	Exact Distance Oracles for Planar Graphs	2012	Shay Mozes Christian Sommer
+ PDF Chat	Improved Distance Queries in Planar Graphs	2011	Yahav Nussbaum
+	Better Tradeoffs for Exact Distance Oracles in Planar Graphs	2017	Paweł Gawrychowski Shay Mozes Oren Weimann Christian Wulff-Nilsen
+	Planar Distance Oracles with Better Time-Space Tradeoffs	2020	Yaowei Long Seth Pettie
+ PDF Chat	Approximate Distance Oracles with Improved Query Time	2013	Christian Wulff‐Nilsen

Works That Cite This (7)

Action	Title	Year	Authors
+ PDF Chat	Fast and Compact Exact Distance Oracle for Planar Graphs	2017	Vincent Cohen-Addad Søren Dahlgaard Christian Wulff‐Nilsen
+ PDF Chat	Efficient Dynamic Approximate Distance Oracles for Vertex-Labeled Planar Graphs	2019	Itay Laish Shay Mozes
+	Constant Query Time $(1 + ε)$-Approximate Distance Oracle for Planar Graphs	2017	Qian‐Ping Gu Gengchun Xu
+ PDF Chat	Efficient Dynamic Approximate Distance Oracles for Vertex-Labeled Planar Graphs	2018	Itay Laish Shay Mozes
+	Fast and Compact Exact Distance Oracle for Planar Graphs	2017	Vincent Cohen-Addad Søren Dahlgaard Christian Wulff‐Nilsen
+ PDF Chat	Covering Planar Metrics (and Beyond): O(1) Trees Suffice	2023	Hsien-Chih Chang Jonathan Conroy Hung Le Lazar Milenković Shay Solomon Cuong Than
+ PDF Chat	Optimal Approximate Distance Oracle for Planar Graphs	2022	Hung Le Christian Wulff‐Nilsen

Works Cited by This (4)

Action	Title	Year	Authors
+	Extremal problems in graph theory	1997	Christopher M. Hartman
+ PDF Chat	Ramsey partitions and proximity data structures	2007	Manor Mendel Assaf Naor
+ PDF Chat	Approximate distance oracles with constant query time	2014	Shiri Chechik
+ PDF Chat	Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs	2011	Ken‐ichi Kawarabayashi Philip N. Klein Christian Sommer