Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Transitive_reduction> ?p ?o. }
Showing items 1 to 30 of
30
with 100 items per page.
- Transitive_reduction abstract "In mathematics, a transitive reduction of a directed graph is a graph with as few edges as possible that has the same reachability relation as the given graph. Equivalently, the given graph and its transitive reduction should have the same transitive closure as each other, and its transitive reduction should have as few edges as possible among all graphs with this property. Transitive reductions were introduced by Aho, Garey & Ullman (1972), who provided tight bounds on the computational complexity of constructing them.If a given graph is a finite directed acyclic graph, its transitive reduction is unique, and is a subgraph of the given graph. However, uniqueness is not guaranteed for graphs with cycles, and for infinite graphs not even existence is guaranteed. The closely related concept of a minimum equivalent graph is a subgraph of the given graph that has the same reachability relation and as few edges as possible. For finite directed acyclic graphs, the minimum equivalent graph is the same as the transitive reduction. However, for graphs that may contain cycles, minimum equivalent graphs are NP-hard to construct, while transitive reductions can still be constructed in polynomial time. Transitive reductions can also be defined for more abstract binary relations on sets, by interpreting the pairs of the relation as arcs in a graph.".
- Transitive_reduction thumbnail Tred-G.svg?width=300.
- Transitive_reduction wikiPageID "3757117".
- Transitive_reduction wikiPageRevisionID "602726846".
- Transitive_reduction hasPhotoCollection Transitive_reduction.
- Transitive_reduction id "TransitiveReduction".
- Transitive_reduction title "Transitive Reduction".
- Transitive_reduction subject Category:Graph_algorithms.
- Transitive_reduction subject Category:Graph_theory.
- Transitive_reduction subject Category:Set_theory.
- Transitive_reduction type Abstraction100002137.
- Transitive_reduction type Act100030358.
- Transitive_reduction type Activity100407535.
- Transitive_reduction type Algorithm105847438.
- Transitive_reduction type Event100029378.
- Transitive_reduction type GraphAlgorithms.
- Transitive_reduction type Procedure101023820.
- Transitive_reduction type PsychologicalFeature100023100.
- Transitive_reduction type Rule105846932.
- Transitive_reduction type YagoPermanentlyLocatedEntity.
- Transitive_reduction comment "In mathematics, a transitive reduction of a directed graph is a graph with as few edges as possible that has the same reachability relation as the given graph. Equivalently, the given graph and its transitive reduction should have the same transitive closure as each other, and its transitive reduction should have as few edges as possible among all graphs with this property.".
- Transitive_reduction label "Transitive reduction".
- Transitive_reduction label "Транзитивное сокращение".
- Transitive_reduction sameAs m.09zc3y.
- Transitive_reduction sameAs Q3088151.
- Transitive_reduction sameAs Q3088151.
- Transitive_reduction sameAs Transitive_reduction.
- Transitive_reduction wasDerivedFrom Transitive_reduction?oldid=602726846.
- Transitive_reduction depiction Tred-G.svg.
- Transitive_reduction isPrimaryTopicOf Transitive_reduction.