Skip to content
ISBN: 3346376494
ISBN13: 9783346376497

Turbo Dijkstra. Finding Single-Source Shortest Paths on Planar Graphs with Nonnegative Edge Weights in Linear Time

ISBN: 3346376494
ISBN13: 9783346376497
Formats

Conditions

Formats

Conditions

See all 1 editions

Book Overview

Seminar paper from the year 2021 in the subject Computer Science - Theory, grade: 1.0 (A), University of Passau, language: English, abstract: The need to find shortest paths in a graph from some fixed source vertex to all other vertices is quite obvious and therefore one of the most important problems in graph theory. For general graphs, the standard way to go is the Dijkstra algorithm. On planar graphs, this approach takes linearithmic time in the number of vertices. However, we present an algorithm published by Henzinger et al. in 1997 that accomplishes the task in linear time on planar graphs.
Format:
Paperback
Language:
English
ISBN:
3346376494
ISBN13:
9783346376497
Release Date:
June 2021
Publisher:
Grin Verlag
Length:
20 Pages
Weight:
0.09 lbs.
Dimensions:
0.1″ × 5.8″ × 8.3″
ComputersComputers & Technology

More by Frieda Von Meding

Customer Reviews

0 customer ratings | 0 reviews
Write a Review

There are currently no reviews. Be the first to review this work.