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

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

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
n9http://dbpedia.org/resource/File:
foafhttp://xmlns.com/foaf/0.1/
n19https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
n13http://commons.wikimedia.org/wiki/Special:FilePath/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
goldhttp://purl.org/linguistics/gold/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Optical_mesh_network
dbo:wikiPageWikiLink
dbr:Edge_disjoint_shortest_pair_algorithm
Subject Item
dbr:Suurballe's_algorithm
dbo:wikiPageWikiLink
dbr:Edge_disjoint_shortest_pair_algorithm
Subject Item
dbr:Edge_disjoint_shortest_pair_algorithm
rdf:type
yago:Act100030358 yago:Procedure101023820 yago:Event100029378 yago:WikicatRoutingAlgorithms dbo:Software yago:Activity100407535 yago:Algorithm105847438 yago:Rule105846932 yago:Abstraction100002137 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity
rdfs:label
Edge disjoint shortest pair algorithm
rdfs:comment
Edge disjoint shortest pair algorithm is an algorithm in computer network routing. The algorithm is used for generating the shortest pair of edge disjoint paths between a given pair of vertices. For an undirected graph G(V, E), it is stated as follows:
foaf:depiction
n13:Bhandari's_Shortest_Pair_of_Edge-Disjoint_Shortest_Paths_Algorithm.jpg
dct:subject
dbc:Routing_algorithms
dbo:wikiPageID
2708054
dbo:wikiPageRevisionID
1077229911
dbo:wikiPageWikiLink
dbr:Vertex_(graph_theory) dbr:Suurballe's_algorithm dbr:Computer_network n9:Bhandari's_Shortest_Pair_of_Edge-Disjoint_Shortest_Paths_Algorithm.jpg dbr:Routing dbc:Routing_algorithms dbr:Algorithm dbr:Dijkstra's_algorithm
owl:sameAs
wikidata:Q5337697 yago-res:Edge_disjoint_shortest_pair_algorithm n19:4izXV freebase:m.07z9t8
dbp:wikiPageUsesTemplate
dbt:More_citations_needed dbt:Reflist dbt:Compu-network-stub
dbo:thumbnail
n13:Bhandari's_Shortest_Pair_of_Edge-Disjoint_Shortest_Paths_Algorithm.jpg?width=300
dbo:abstract
Edge disjoint shortest pair algorithm is an algorithm in computer network routing. The algorithm is used for generating the shortest pair of edge disjoint paths between a given pair of vertices. For an undirected graph G(V, E), it is stated as follows: 1. * Run the shortest path algorithm for the given pair of vertices 2. * Replace each edge of the shortest path (equivalent to two oppositely directed arcs) by a single arc directed towards the source vertex 3. * Make the length of each of the above arcs negative 4. * Run the shortest path algorithm (Note: the algorithm should accept negative costs) 5. * Erase the overlapping edges of the two paths found, and reverse the direction of the remaining arcs on the first shortest path such that each arc on it is directed towards the destination vertex now. The desired pair of paths results. In lieu of the general purpose Ford's shortest path algorithm valid for negative arcs present anywhere in a graph (with nonexistent negative cycles), Bhandari provides two different algorithms, either one of which can be used in Step 4. One algorithm is a slight modification of the traditional Dijkstra's algorithm, and the other called the Breadth-First-Search (BFS) algorithm is a variant of the Moore's algorithm. Because the negative arcs are only on the first shortest path, no negative cycle arises in the transformed graph (Steps 2 and 3). In a nonnegative graph, the modified Dijkstra algorithm reduces to the traditional Dijkstra's algorithm, and can therefore be used in Step 1 of the above algorithm (and similarly, the BFS algorithm).
gold:hypernym
dbr:Algorithm
prov:wasDerivedFrom
wikipedia-en:Edge_disjoint_shortest_pair_algorithm?oldid=1077229911&ns=0
dbo:wikiPageLength
8401
foaf:isPrimaryTopicOf
wikipedia-en:Edge_disjoint_shortest_pair_algorithm
Subject Item
dbr:Edge_Disjoint_Shortest_Pair_Algorithm
dbo:wikiPageWikiLink
dbr:Edge_disjoint_shortest_pair_algorithm
dbo:wikiPageRedirects
dbr:Edge_disjoint_shortest_pair_algorithm
Subject Item
dbr:Routing
dbo:wikiPageWikiLink
dbr:Edge_disjoint_shortest_pair_algorithm
Subject Item
wikipedia-en:Edge_disjoint_shortest_pair_algorithm
foaf:primaryTopic
dbr:Edge_disjoint_shortest_pair_algorithm