This HTML5 document contains 30 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n6https://global.dbpedia.org/id/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
dbphttp://dbpedia.org/property/
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/
n8https://docs.scipy.org/doc/numpy/reference/generated/

Statements

Subject Item
dbr:Shortest_path_problem
dbo:wikiPageWikiLink
dbr:Seidel's_algorithm
Subject Item
dbr:Seidel's_algorithm
rdfs:label
Seidel's algorithm
rdfs:comment
Seidel's algorithm is an algorithm designed by Raimund Seidel in 1992 for the all-pairs-shortest-path problem for undirected, unweighted, connected graphs. It solves the problem in expected time for a graph with vertices, where is the exponent in the complexity of matrix multiplication. If only the distances between each pair of vertices are sought, the same time bound can be achieved in the worst case. Even though the algorithm is designed for connected graphs, it can be applied individually to each connected component of a graph with the same running time overall. There is an exception to the expected running time given above for computing the paths: if the expected running time becomes .
dcterms:subject
dbc:Graph_algorithms dbc:Graph_distance dbc:Computational_problems_in_graph_theory dbc:Polynomial-time_problems dbc:Articles_with_example_Python_(programming_language)_code
dbo:wikiPageID
55206702
dbo:wikiPageRevisionID
1068926046
dbo:wikiPageWikiLink
dbc:Graph_algorithms dbc:Graph_distance dbr:Adjacency_matrix dbc:Articles_with_example_Python_(programming_language)_code dbr:Shortest_path_problem dbr:Computational_complexity_of_matrix_multiplication dbr:Las_Vegas_algorithm dbc:Polynomial-time_problems dbr:Connected_component_(graph_theory) dbc:Computational_problems_in_graph_theory dbr:Raimund_Seidel
dbo:wikiPageExternalLink
n8:numpy.matrix.html
owl:sameAs
n6:3f69u wikidata:Q39486959
dbp:wikiPageUsesTemplate
dbt:Reflist
dbo:abstract
Seidel's algorithm is an algorithm designed by Raimund Seidel in 1992 for the all-pairs-shortest-path problem for undirected, unweighted, connected graphs. It solves the problem in expected time for a graph with vertices, where is the exponent in the complexity of matrix multiplication. If only the distances between each pair of vertices are sought, the same time bound can be achieved in the worst case. Even though the algorithm is designed for connected graphs, it can be applied individually to each connected component of a graph with the same running time overall. There is an exception to the expected running time given above for computing the paths: if the expected running time becomes .
prov:wasDerivedFrom
wikipedia-en:Seidel's_algorithm?oldid=1068926046&ns=0
dbo:wikiPageLength
5215
foaf:isPrimaryTopicOf
wikipedia-en:Seidel's_algorithm
Subject Item
wikipedia-en:Seidel's_algorithm
foaf:primaryTopic
dbr:Seidel's_algorithm