Matches in DBpedia 2015-04 for { <http://dbpedia.org/resource/Widest_path_problem> ?p ?o }
Showing triples 1 to 36 of
36
with 100 triples per page.
- Widest_path_problem abstract "In graph algorithms, the widest path problem, also known as the bottleneck shortest path problem or the maximum capacity path problem, is the problem of finding a path between two designated vertices in a weighted graph, maximizing the weight of the minimum-weight edge in the path.For instance, if the graph represents connections between routers in the Internet, and the weight of an edge represents the bandwidth of a connection between two routers, the widest path problem is the problem of finding an end-to-end path between two Internet nodes that has the maximum possible bandwidth. The weight of the minimum-weight edge is known as the capacity or bandwidth of the path. As well as its applications in network routing, the widest path problem is also an important component of the Schulze method for deciding the winner of a multiway election, and has been applied to digital compositing, metabolic analysis, and the computation of maximum flows. It is possible to adapt most shortest path algorithms to compute widest paths, by modifying them to use the bottleneck distance instead of path length. However, in many cases even faster algorithms are possible.A closely related problem, the minimax path problem, asks for the path that minimizes the maximum weight of any of its edges. It has applications that include transportation planning. Any algorithm for the widest path problem can be transformed into an algorithm for the minimax path problem, or vice versa, by reversing the sense of all the weight comparisons performed by the algorithm, or equivalently by replacing every edge weight by its negation.".
- Widest_path_problem thumbnail CPT-Graphs-undirected-weighted.svg?width=300.
- Widest_path_problem wikiPageExternalLink 6580214.
- Widest_path_problem wikiPageID "31567349".
- Widest_path_problem wikiPageRevisionID "607760350".
- Widest_path_problem hasPhotoCollection Widest_path_problem.
- Widest_path_problem subject Category:Computational_problems_in_graph_theory.
- Widest_path_problem subject Category:Graph_algorithms.
- Widest_path_problem subject Category:Network_theory.
- Widest_path_problem subject Category:Polynomial-time_problems.
- Widest_path_problem type Abstraction100002137.
- Widest_path_problem type Act100030358.
- Widest_path_problem type Activity100407535.
- Widest_path_problem type Algorithm105847438.
- Widest_path_problem type Attribute100024264.
- Widest_path_problem type ComputationalProblemsInGraphTheory.
- Widest_path_problem type Condition113920835.
- Widest_path_problem type Difficulty114408086.
- Widest_path_problem type Event100029378.
- Widest_path_problem type GraphAlgorithms.
- Widest_path_problem type Polynomial-timeProblems.
- Widest_path_problem type Problem114410605.
- Widest_path_problem type Procedure101023820.
- Widest_path_problem type PsychologicalFeature100023100.
- Widest_path_problem type Rule105846932.
- Widest_path_problem type State100024720.
- Widest_path_problem type YagoPermanentlyLocatedEntity.
- Widest_path_problem comment "In graph algorithms, the widest path problem, also known as the bottleneck shortest path problem or the maximum capacity path problem, is the problem of finding a path between two designated vertices in a weighted graph, maximizing the weight of the minimum-weight edge in the path.For instance, if the graph represents connections between routers in the Internet, and the weight of an edge represents the bandwidth of a connection between two routers, the widest path problem is the problem of finding an end-to-end path between two Internet nodes that has the maximum possible bandwidth. ".
- Widest_path_problem label "Widest path problem".
- Widest_path_problem sameAs m.0glrt2m.
- Widest_path_problem sameAs Q7998708.
- Widest_path_problem sameAs Q7998708.
- Widest_path_problem sameAs Widest_path_problem.
- Widest_path_problem wasDerivedFrom Widest_path_problem?oldid=607760350.
- Widest_path_problem depiction CPT-Graphs-undirected-weighted.svg.
- Widest_path_problem isPrimaryTopicOf Widest_path_problem.