2013 | OriginalPaper | Buchkapitel
On the Stretch Factor of the Theta-4 Graph
verfasst von : Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, André van Renssen, Sander Verdonschot
Erschienen in: Algorithms and Data Structures
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper we show that the
θ
-graph with 4 cones has constant stretch factor, i.e., there is a path between any pair of vertices in this graph whose length is at most a constant times the Euclidean distance between that pair of vertices. This is the last
θ
-graph for which it was not known whether its stretch factor was bounded.