Efficient vertex-label distance oracles for planar graphs (Q1743124): Difference between revisions

Latest revision as of 12:00, 15 July 2024

scientific article; zbMATH DE number 6545969

Efficient Vertex-Label Distance Oracles for Planar Graphs

Language	Label	Description	Also known as
English	Efficient vertex-label distance oracles for planar graphs	scientific article; zbMATH DE number 6545969	Efficient Vertex-Label Distance Oracles for Planar Graphs

Statements

instance of

scholarly article

0 references

title

Efficient vertex-label distance oracles for planar graphs (English)

0 references

Efficient Vertex-Label Distance Oracles for Planar Graphs (English)

0 references

zbMATH Open document ID

1390.68507

0 references

1383.68065

0 references

DOI

10.1007/s00224-017-9827-0

0 references

10.1007/978-3-319-28684-6_9

0 references

0 references

0 references

Theory of Computing Systems

0 references

Approximation and Online Algorithms

0 references

publication date

12 April 2018

0 references

26 February 2016

0 references

full work available at URL

https://arxiv.org/abs/1504.04690

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

planar graphs

0 references

approximate distance oracles

0 references

portals

0 references

shortest-path separators

0 references

MaRDI profile type

MaRDI publication profile

0 references

0 references

0 references

0 references

0 references

0 references

Approximate Nearest Neighbor Search in Metrics of Planar Graphs

0 references

Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error

0 references

Approximate distance oracles for unweighted graphs in expected O ( n 2 ) time

0 references

Improved Distance Oracles and Spanners for Vertex-Labeled Graphs

0 references

Approximate Distance Oracles with Improved Bounds

0 references

Planar separators and parallel polygon triangulation.

0 references

Deterministic Dictionaries

0 references

Fast Algorithms for Finding Nearest Common Ancestors

0 references

Faster shortest-path algorithms for planar graphs

0 references

Distance Oracles for Vertex-Labeled Graphs

0 references

Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs

0 references

More Compact Oracles for Approximate Distances in Undirected Planar Graphs

0 references

Q4829018

0 references

Structured recursive separator decompositions for planar graphs in linear time

0 references

(1 + ε)-Distance Oracles for Vertex-Labeled Planar Graphs

0 references

A Separator Theorem for Planar Graphs

0 references

The Power of Dynamic Distance Oracles

0 references

Efficient vertex-label distance oracles for planar graphs

0 references

Distance Oracles beyond the Thorup--Zwick Bound

0 references

Constructing Efficient Dictionaries in Close to Sorting Time

0 references

Compact oracles for reachability and approximate distances in planar digraphs

0 references

Approximate distance oracles

0 references

Log-logarithmic worst-case range queries are possible in space theta(N)

0 references

Q5743389

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1743124

@@ Property / cites work @@
+Approximate Nearest Neighbor Search in Metrics of Planar Graphs
+Normal rank
@@ Property / cites work @@
+Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
+Normal rank
@@ Property / cites work @@
+Approximate distance oracles for unweighted graphs in expected             <i>O</i>             (             <i>n</i>             <sup>2</sup>             ) time
+Normal rank
@@ Property / cites work @@
+Improved Distance Oracles and Spanners for Vertex-Labeled Graphs
+Normal rank
@@ Property / cites work @@
+Approximate Distance Oracles with Improved Bounds
@@ Property / cites work: Approximate Distance Oracles with Improved Bounds / rank @@
+Normal rank
@@ Property / cites work @@
+Planar separators and parallel polygon triangulation.
+Normal rank
@@ Property / cites work @@
+Deterministic Dictionaries
@@ Property / cites work: Deterministic Dictionaries / rank @@
+Normal rank
@@ Property / cites work @@
+Fast Algorithms for Finding Nearest Common Ancestors
+Normal rank
@@ Property / cites work @@
+Faster shortest-path algorithms for planar graphs
@@ Property / cites work: Faster shortest-path algorithms for planar graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Distance Oracles for Vertex-Labeled Graphs
@@ Property / cites work: Distance Oracles for Vertex-Labeled Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs
+Normal rank
@@ Property / cites work @@
+More Compact Oracles for Approximate Distances in Undirected Planar Graphs
+Normal rank
@@ Property / cites work @@
+Q4829018
@@ Property / cites work: Q4829018 / rank @@
+Normal rank
@@ Property / cites work @@
+Structured recursive separator decompositions for planar graphs in linear time
+Normal rank
@@ Property / cites work @@
+(1 + ε)-Distance Oracles for Vertex-Labeled Planar Graphs
+Normal rank
@@ Property / cites work @@
+A Separator Theorem for Planar Graphs
@@ Property / cites work: A Separator Theorem for Planar Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The Power of Dynamic Distance Oracles
@@ Property / cites work: The Power of Dynamic Distance Oracles / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient vertex-label distance oracles for planar graphs
+Normal rank
@@ Property / cites work @@
+Distance Oracles beyond the Thorup--Zwick Bound
@@ Property / cites work: Distance Oracles beyond the Thorup--Zwick Bound / rank @@
+Normal rank
@@ Property / cites work @@
+Constructing Efficient Dictionaries in Close to Sorting Time
+Normal rank
@@ Property / cites work @@
+Compact oracles for reachability and approximate distances in planar digraphs
+Normal rank
@@ Property / cites work @@
+Approximate distance oracles
@@ Property / cites work: Approximate distance oracles / rank @@
+Normal rank
@@ Property / cites work @@
+Log-logarithmic worst-case range queries are possible in space theta(N)
+Normal rank
@@ Property / cites work @@
+Q5743389
@@ Property / cites work: Q5743389 / rank @@
+Normal rank