http://dbpedia.org/ontology/abstract
|
A central problem in algorithmic graph the … A central problem in algorithmic graph theory is the shortest path problem. Hereby, the problem of finding the shortest path between every pair of nodes is known as all-pair-shortest-paths (APSP) problem. As sequential algorithms for this problem often yield long runtimes, parallelization has shown to be beneficial in this field. In this article two efficient algorithms solving this problem are introduced. Another variation of the problem is the single-source-shortest-paths (SSSP) problem, which also has parallel approaches: Parallel single-source shortest path algorithm.lel single-source shortest path algorithm.
, Parallele All-Pair-Shortest-Paths-Algorith … Parallele All-Pair-Shortest-Paths-Algorithmen sind Algorithmen in der Graphentheorie, um kürzeste Wege zwischen zwei Knoten zu finden. Die kürzesten Wege zwischen allen Knoten in einem Graphen zu finden, bezeichnet man als All-Pairs-Shortest-Path-Problem. Da bei sequentiellen Algorithmen, die dieses Problem lösen, große Graphen zu langen Laufzeiten führen, lohnt es sich diese zu parallelisieren. Hier werden Techniken zur Parallelisierung für die bekanntesten Algorithmen und deren Auswirkungen auf die Laufzeiten vorgestellt.swirkungen auf die Laufzeiten vorgestellt.
|
http://dbpedia.org/ontology/thumbnail
|
http://commons.wikimedia.org/wiki/Special:FilePath/Apsp_dijkstra_graph.png?width=300 +
|
http://dbpedia.org/ontology/wikiPageExternalLink
|
http://www.cs.cornell.edu/~bindel/class/cs5220-f11/code/path.pdf +
, http://www.academia.edu/download/46545236/Scalability_of_parallel_algorithms_for_t20160616-15656-rc5uyt.pdf +
|
http://dbpedia.org/ontology/wikiPageID
|
56993742
|
http://dbpedia.org/ontology/wikiPageLength
|
17905
|
http://dbpedia.org/ontology/wikiPageRevisionID
|
1098932192
|
http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Category:Graph_algorithms +
, http://dbpedia.org/resource/File:Apsp_dijkstra_graph.png +
, http://dbpedia.org/resource/File:Data-denpendencies-floyd.png +
, http://dbpedia.org/resource/File:2d_block-mapping.png +
, http://dbpedia.org/resource/File:Apsp_dijkstra_distancelist.png +
, http://dbpedia.org/resource/Reduce-operation +
, http://dbpedia.org/resource/Shortest_path_problem +
, http://dbpedia.org/resource/Floyd%E2%80%93Warshall_algorithm +
, http://dbpedia.org/resource/Parallel_single-source_shortest_path_algorithm +
, http://dbpedia.org/resource/Adjacency_matrix +
, http://dbpedia.org/resource/Graph_theory +
, http://dbpedia.org/resource/Floyd_algorithm +
, http://dbpedia.org/resource/Dijkstra_algorithm +
, http://dbpedia.org/resource/Sequential_algorithm +
|
http://dbpedia.org/property/bot
|
medic
|
http://dbpedia.org/property/date
|
July 2022
|
http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Multiple_issues +
, http://dbpedia.org/resource/Template:Dead_link +
, http://dbpedia.org/resource/Template:No_footnotes +
, http://dbpedia.org/resource/Template:Manual +
, http://dbpedia.org/resource/Template:Reflist +
, http://dbpedia.org/resource/Template:Cbignore +
, http://dbpedia.org/resource/Template:Orphan +
|
http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Graph_algorithms +
|
http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Parallel_all-pairs_shortest_path_algorithm?oldid=1098932192&ns=0 +
|
http://xmlns.com/foaf/0.1/depiction
|
http://commons.wikimedia.org/wiki/Special:FilePath/Data-denpendencies-floyd.png +
, http://commons.wikimedia.org/wiki/Special:FilePath/Apsp_dijkstra_distancelist.png +
, http://commons.wikimedia.org/wiki/Special:FilePath/Apsp_dijkstra_graph.png +
, http://commons.wikimedia.org/wiki/Special:FilePath/2d_block-mapping.png +
|
http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Parallel_all-pairs_shortest_path_algorithm +
|
owl:sameAs |
http://dbpedia.org/resource/Parallel_all-pairs_shortest_path_algorithm +
, http://de.dbpedia.org/resource/Parallele_All-Pair-Shortest-Paths-Algorithmen +
, https://global.dbpedia.org/id/5jDXw +
, http://www.wikidata.org/entity/Q51173345 +
|
rdfs:comment |
Parallele All-Pair-Shortest-Paths-Algorith … Parallele All-Pair-Shortest-Paths-Algorithmen sind Algorithmen in der Graphentheorie, um kürzeste Wege zwischen zwei Knoten zu finden. Die kürzesten Wege zwischen allen Knoten in einem Graphen zu finden, bezeichnet man als All-Pairs-Shortest-Path-Problem. Da bei sequentiellen Algorithmen, die dieses Problem lösen, große Graphen zu langen Laufzeiten führen, lohnt es sich diese zu parallelisieren. Hier werden Techniken zur Parallelisierung für die bekanntesten Algorithmen und deren Auswirkungen auf die Laufzeiten vorgestellt.swirkungen auf die Laufzeiten vorgestellt.
, A central problem in algorithmic graph the … A central problem in algorithmic graph theory is the shortest path problem. Hereby, the problem of finding the shortest path between every pair of nodes is known as all-pair-shortest-paths (APSP) problem. As sequential algorithms for this problem often yield long runtimes, parallelization has shown to be beneficial in this field. In this article two efficient algorithms solving this problem are introduced. Another variation of the problem is the single-source-shortest-paths (SSSP) problem, which also has parallel approaches: Parallel single-source shortest path algorithm.lel single-source shortest path algorithm.
|
rdfs:label |
Parallele All-Pair-Shortest-Paths-Algorithmen
, Parallel all-pairs shortest path algorithm
|