Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Unique_sink_orientation> ?p ?o. }
Showing items 1 to 16 of
16
with 100 items per page.
- Unique_sink_orientation abstract "In mathematics, a unique sink orientation is an orientation of the edges of a polytope such that, in every face of the polytope (including the whole polytope as one of the faces), there is exactly one vertex for which all adjoining edges are oriented inward (i.e. towards that vertex). If a polytope is given together with a linear objective function, and edges are oriented from vertices with smaller objective function values to vertices with larger objective values, the result is a unique sink orientation. Thus, unique sink orientations can be used to model linear programs as well as certain nonlinear programs such as the smallest circle problem.The problem of finding the sink in a unique sink orientation of a hypercube was formulated as an abstraction of linear complementarity problems by Stickney & Watson (1978).It is possible for an algorithm to determine the unique sink of a d-dimensional hypercube in time cd for c < 2, substantially smaller than the 2d time required to examine all vertices. When the orientation has the additional property that the orientation forms a directed acyclic graph, which happens when unique sink orientations are used to model LP-type problems, it is possible to find the sink using a randomized algorithm in expected time exponential in the square root of d (Szabó & Welzl 2001).".
- Unique_sink_orientation wikiPageID "18476346".
- Unique_sink_orientation wikiPageRevisionID "476361207".
- Unique_sink_orientation hasPhotoCollection Unique_sink_orientation.
- Unique_sink_orientation subject Category:Graph_theory_objects.
- Unique_sink_orientation type GraphTheoryObjects.
- Unique_sink_orientation type Object100002684.
- Unique_sink_orientation type PhysicalEntity100001930.
- Unique_sink_orientation comment "In mathematics, a unique sink orientation is an orientation of the edges of a polytope such that, in every face of the polytope (including the whole polytope as one of the faces), there is exactly one vertex for which all adjoining edges are oriented inward (i.e. towards that vertex).".
- Unique_sink_orientation label "Unique sink orientation".
- Unique_sink_orientation sameAs m.04f183k.
- Unique_sink_orientation sameAs Q7886959.
- Unique_sink_orientation sameAs Q7886959.
- Unique_sink_orientation sameAs Unique_sink_orientation.
- Unique_sink_orientation wasDerivedFrom Unique_sink_orientation?oldid=476361207.
- Unique_sink_orientation isPrimaryTopicOf Unique_sink_orientation.