Near-Optimal Distance Emulator for Planar Graphs

Hsien-Chih Chang, Paweł Gawrychowski, Shay Mozes, Oren Weimann

Type: Preprint

Publication Date: 2018-01-01

Citations: 0

DOI: https://doi.org/10.48550/arxiv.1807.01478

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Near-Optimal Distance Emulator for Planar Graphs	2018	Hsien-Chih Chang Paweł Gawrychowski Shay Mozes Oren Weimann
+	Near-Linear $\varepsilon$-Emulators for Planar Graphs	2022	Hsien-Chih Chang Robert Krauthgamer Zihan Tan
+	Optimal Approximate Distance Oracle for Planar Graphs	2021	Hung Le Christian Wulff‐Nilsen
+	Near-Optimal Distance Oracles for Vertex-Labeled Planar Graphs	2021	Jacob Evald Viktor Fredslund-Hansen Christian Wulff‐Nilsen
+	A note on distance labeling in planar graphs	2016	Paweł Gawrychowski Przemysław Uznański
+	Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs	2020	Viktor Fredslund-Hansen Shay Mozes Christian Wulff‐Nilsen
+	Efficient Vertex-Label Distance Oracles for Planar Graphs	2015	Shay Mozes Eyal E. Skop
+	Efficient Vertex-Label Distance Oracles for Planar Graphs	2015	Shay Mozes Eyal E. Skop
+	Constant Query Time $(1 + ε)$-Approximate Distance Oracle for Planar Graphs	2017	Qian‐Ping Gu Gengchun Xu
+	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	Parameterized Complexity of Finding Dissimilar Shortest Paths	2024	Ryo Funayama Yasuaki Kobayashi Takeaki Uno
+ PDF Chat	Preserving Terminal Distances Using Minors	2014	Robert Krauthgamer Huy L. Nguyễn Tamar Zondiner
+	Approximation Algorithms and Hardness for $n$-Pairs Shortest Paths and All-Nodes Shortest Cycles	2022	Mina Dalirooyfard Ce Jin Virginia Vassilevska Williams Nicole Wein
+	An $O(\log k)$-Approximation for Directed Steiner Tree in Planar Graphs	2023	Zachary Friggstad Ramin Mousavi
+ PDF Chat	Massively Parallel Algorithms for Approximate Shortest Paths	2024	Michal Dory Shaked Matar
+	Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds	2016	Yun Kuen Cheung Gramoz Goranci Monika Henzinger
+	Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds	2016	Yun Kuen Cheung Gramoz Goranci Monika Henzinger
+	Exact Distance Oracles for Planar Graphs	2010	Shay Mozes Christian Sommer
+ PDF Chat	Constant Query Time $$(1+\epsilon )$$ -Approximate Distance Oracle for Planar Graphs	2015	Qian‐Ping Gu Gengchun Xu

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (16)

Action	Title	Year	Authors
+	On embedding graphs in squashed cubes	1972	R. L. Graham H. O. Pollak
+ PDF Chat	Preserving Terminal Distances Using Minors	2014	Robert Krauthgamer Huy L. Nguyễn Tamar Zondiner
+	Fast distance multiplication of unit-Monge matrices	2010	Alexander Tiskin
+	Geometric applications of a matrix-searching algorithm	1987	Alok Aggarwal Maria Klawe Shlomo Moran Peter W. Shor Robert Wilber
+ PDF Chat	On minimal <i>n</i>-universal graphs	1965	J. W. Moon
+ PDF Chat	Structured recursive separator decompositions for planar graphs in linear time	2013	Philip N. Klein Shay Mozes Christian Sommer
+ PDF Chat	A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs	2016	Michael Elkin Seth Pettie
+	Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds	2016	Yun Kuen Cheung Gramoz Goranci Monika Henzinger
+ PDF Chat	Near-Optimal Compression for the Planar Graph Metric	2018	Amir Abboud Paweł Gawrychowski Shay Mozes Oren Weimann
+ PDF Chat	The 4/3 Additive Spanner Exponent Is Tight	2017	Amir Abboud Greg Bodwin