𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Shortest paths for line segments

✍ Scribed by Christian Icking; Günter Rote; Emo Welzl; Chee Yap

Publisher
Springer
Year
1993
Tongue
English
Weight
1007 KB
Volume
10
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Alternating paths through disjoint line
Alternating paths through disjoint line segments
✍ Michael Hoffmann; Csaba D Tóth 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 265 KB

We show that every segment endpoint visibility graph on n disjoint line segments in the plane admits an alternating path of length (log n), and this bound is optimal apart from a constant factor.

Inapproximability results for the invers
Inapproximability results for the inverse shortest paths problem with integer lengths and unique shortest paths
✍ Andreas Bley 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 304 KB

## Abstract We study the complexity of two inverse shortest paths (ISP) problems with integer arc lengths and the requirement for uniquely determined shortest paths. Given a collection of paths in a directed graph __D__ = (__V__, __A__), the task is to find positive integer arc lengths such that th

Using Selective Path-Doubling for Parall
Using Selective Path-Doubling for Parallel Shortest-Path Computations
✍ Edith Cohen 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 291 KB

We 1 consider parallel shortest-paths computations in weighted undirected graphs Ž . < < < < Ž 3 . Gs V, E , where n s V and m s E . The standard O n work path-doubling Ž . Ž . Floyd-Warshall algorithm consists of O log n phases, where in each phase, for Ž . 3 every triplet of vertices u , u , u g V

Fully Dynamic Algorithms for Maintaining
Fully Dynamic Algorithms for Maintaining Shortest Paths Trees
✍ Daniele Frigioni; Alberto Marchetti-Spaccamela; Umberto Nanni 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 213 KB

We propose fully dynamic algorithms for maintaining the distances and the shortest paths from a single source in either a directed or an undirected graph with positive real edge weights, handling insertions, deletions, and weight updates of edges. The algorithms require linear space and optimal quer