Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Transitive_reduction> ?p ?o }
Showing triples 1 to 77 of
77
with 100 triples 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 wikiPageLength "11143".
- Transitive_reduction wikiPageOutDegree "41".
- Transitive_reduction wikiPageRevisionID "683278956".
- Transitive_reduction wikiPageWikiLink Adjacency_matrix.
- Transitive_reduction wikiPageWikiLink Binary_relation.
- Transitive_reduction wikiPageWikiLink Breadth-first_search.
- Transitive_reduction wikiPageWikiLink Breadth_first_search.
- Transitive_reduction wikiPageWikiLink Category:Graph_algorithms.
- Transitive_reduction wikiPageWikiLink Category:Graph_theory.
- Transitive_reduction wikiPageWikiLink Category:Set_theory.
- Transitive_reduction wikiPageWikiLink Covering_relation.
- Transitive_reduction wikiPageWikiLink Cycle_(graph_theory).
- Transitive_reduction wikiPageWikiLink Dense_graph.
- Transitive_reduction wikiPageWikiLink Depth-first_search.
- Transitive_reduction wikiPageWikiLink Depth_first_search.
- Transitive_reduction wikiPageWikiLink Directed_acyclic_graph.
- Transitive_reduction wikiPageWikiLink Directed_cycle.
- Transitive_reduction wikiPageWikiLink Directed_graph.
- Transitive_reduction wikiPageWikiLink Glossary_of_graph_theory.
- Transitive_reduction wikiPageWikiLink Hamiltonian_cycle.
- Transitive_reduction wikiPageWikiLink Hamiltonian_path.
- Transitive_reduction wikiPageWikiLink Hasse_diagram.
- Transitive_reduction wikiPageWikiLink Induced_subgraph.
- Transitive_reduction wikiPageWikiLink Journal_of_the_ACM.
- Transitive_reduction wikiPageWikiLink Linear_time.
- Transitive_reduction wikiPageWikiLink Logical_matrix.
- Transitive_reduction wikiPageWikiLink Longest_path_problem.
- Transitive_reduction wikiPageWikiLink Mathematics.
- Transitive_reduction wikiPageWikiLink Matrix_multiplication.
- Transitive_reduction wikiPageWikiLink NP-hard.
- Transitive_reduction wikiPageWikiLink NP-hardness.
- Transitive_reduction wikiPageWikiLink Ordered_pair.
- Transitive_reduction wikiPageWikiLink Partially_ordered_set.
- Transitive_reduction wikiPageWikiLink Polynomial_time.
- Transitive_reduction wikiPageWikiLink Reachability.
- Transitive_reduction wikiPageWikiLink SIAM_Journal_on_Computing.
- Transitive_reduction wikiPageWikiLink Set_(mathematics).
- Transitive_reduction wikiPageWikiLink Sparse_graph.
- Transitive_reduction wikiPageWikiLink Strongly_connected_component.
- Transitive_reduction wikiPageWikiLink Time_complexity.
- Transitive_reduction wikiPageWikiLink Transitive_closure.
- Transitive_reduction wikiPageWikiLink File:Tred-G.svg.
- Transitive_reduction wikiPageWikiLink File:Tred-Gprime.svg.
- Transitive_reduction wikiPageWikiLinkText "Transitive reduction".
- Transitive_reduction wikiPageWikiLinkText "transitive reduction".
- Transitive_reduction wikiPageWikiLinkText "transitively reduced".
- Transitive_reduction hasPhotoCollection Transitive_reduction.
- Transitive_reduction id "TransitiveReduction".
- Transitive_reduction title "Transitive Reduction".
- Transitive_reduction wikiPageUsesTemplate Template:Citation.
- Transitive_reduction wikiPageUsesTemplate Template:Harvtxt.
- Transitive_reduction wikiPageUsesTemplate Template:Mathworld.
- Transitive_reduction wikiPageUsesTemplate Template:Reflist.
- Transitive_reduction wikiPageUsesTemplate Template:Sfnp.
- Transitive_reduction subject Category:Graph_algorithms.
- Transitive_reduction subject Category:Graph_theory.
- Transitive_reduction subject Category:Set_theory.
- Transitive_reduction hypernym Graph.
- Transitive_reduction type Software.
- Transitive_reduction type Algorithm.
- Transitive_reduction type Combinatoric.
- Transitive_reduction type Field.
- Transitive_reduction type Relation.
- 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 sameAs m.09zc3y.
- Transitive_reduction sameAs Транзитивное_сокращение.
- Transitive_reduction sameAs Tranzitivna_redukcija.
- Transitive_reduction sameAs Транзитивне_скорочення.
- Transitive_reduction sameAs Q3088151.
- Transitive_reduction sameAs Q3088151.
- Transitive_reduction wasDerivedFrom Transitive_reduction?oldid=683278956.
- Transitive_reduction depiction Tred-G.svg.
- Transitive_reduction isPrimaryTopicOf Transitive_reduction.