Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Matroid_oracle> ?p ?o }
Showing triples 1 to 95 of
95
with 100 triples per page.
- Matroid_oracle abstract "In mathematics and computer science, a matroid oracle is a subroutine through which an algorithm may access a matroid, an abstract combinatorial structure that can be used to describe the linear dependencies between vectors in a vector space or the spanning trees of a graph, among other applications.The most commonly used oracle of this type is an independence oracle, a subroutine for testing whether a set of matroid elements is independent. Several other types of oracle have also been used; some of them have been shown to be weaker than independence oracles, some stronger, and some equivalent in computational power.Many algorithms that perform computations on matroids have been designed to take an oracle as input, allowing them to run efficiently without change on many different kinds of matroids, and without additional assumptions about what kind of matroid they are using. For instance, given an independence oracle for any matroid, it is possible to find the minimum weight basis of the matroid by applying a greedy algorithm that adds elements to the basis in sorted order by weight, using the independence oracle to test whether each element can be added.In computational complexity theory, the oracle model has led to unconditional lower bounds proving that certain matroid problems cannot be solved in polynomial time, without invoking unproved assumptions such as the assumption that P ≠ NP. Problems that have been shown to be hard in this way include testing whether a matroid is binary or uniform, or testing whether it contains certain fixed minors.".
- Matroid_oracle wikiPageExternalLink matroiddecompositionbook.pdf.
- Matroid_oracle wikiPageExternalLink 66398.
- Matroid_oracle wikiPageID "36878315".
- Matroid_oracle wikiPageLength "33517".
- Matroid_oracle wikiPageOutDegree "73".
- Matroid_oracle wikiPageRevisionID "675336619".
- Matroid_oracle wikiPageWikiLink Algorithm.
- Matroid_oracle wikiPageWikiLink Automorphism.
- Matroid_oracle wikiPageWikiLink Automorphism_group.
- Matroid_oracle wikiPageWikiLink Bicircular_matroid.
- Matroid_oracle wikiPageWikiLink Binary_matroid.
- Matroid_oracle wikiPageWikiLink Bipartite_matroid.
- Matroid_oracle wikiPageWikiLink Black_box_group.
- Matroid_oracle wikiPageWikiLink Boolean_data_type.
- Matroid_oracle wikiPageWikiLink Boolean_value.
- Matroid_oracle wikiPageWikiLink Branch-decomposition.
- Matroid_oracle wikiPageWikiLink Canadian_Journal_of_Mathematics.
- Matroid_oracle wikiPageWikiLink Category:Matroid_theory.
- Matroid_oracle wikiPageWikiLink Combinatorica.
- Matroid_oracle wikiPageWikiLink Computational_complexity_theory.
- Matroid_oracle wikiPageWikiLink Discrete_Mathematics_(journal).
- Matroid_oracle wikiPageWikiLink Double_exponential_function.
- Matroid_oracle wikiPageWikiLink Dual_matroid.
- Matroid_oracle wikiPageWikiLink Ear_decomposition.
- Matroid_oracle wikiPageWikiLink Empty_set.
- Matroid_oracle wikiPageWikiLink Eulerian_matroid.
- Matroid_oracle wikiPageWikiLink Field_(mathematics).
- Matroid_oracle wikiPageWikiLink Gammoid.
- Matroid_oracle wikiPageWikiLink Graph_(mathematics).
- Matroid_oracle wikiPageWikiLink Graphic_matroid.
- Matroid_oracle wikiPageWikiLink Greedy_algorithm.
- Matroid_oracle wikiPageWikiLink Group_theory.
- Matroid_oracle wikiPageWikiLink Implicit_graph.
- Matroid_oracle wikiPageWikiLink Independence_system.
- Matroid_oracle wikiPageWikiLink Indicator_function.
- Matroid_oracle wikiPageWikiLink Information_Processing_Letters.
- Matroid_oracle wikiPageWikiLink Journal_of_Combinatorial_Theory.
- Matroid_oracle wikiPageWikiLink Journal_of_Computer_and_System_Sciences.
- Matroid_oracle wikiPageWikiLink Linear_independence.
- Matroid_oracle wikiPageWikiLink Linear_matroid.
- Matroid_oracle wikiPageWikiLink Lower_bound.
- Matroid_oracle wikiPageWikiLink Matching_(graph_theory).
- Matroid_oracle wikiPageWikiLink Mathematical_Optimization_Society.
- Matroid_oracle wikiPageWikiLink Mathematical_Programming_(journal).
- Matroid_oracle wikiPageWikiLink Matrix_(mathematics).
- Matroid_oracle wikiPageWikiLink Matroid.
- Matroid_oracle wikiPageWikiLink Matroid_intersection.
- Matroid_oracle wikiPageWikiLink Matroid_minor.
- Matroid_oracle wikiPageWikiLink Matroid_rank.
- Matroid_oracle wikiPageWikiLink Matroid_representation.
- Matroid_oracle wikiPageWikiLink Oracle_machine.
- Matroid_oracle wikiPageWikiLink Oriented_matroid.
- Matroid_oracle wikiPageWikiLink P_versus_NP_problem.
- Matroid_oracle wikiPageWikiLink Parallel_algorithm.
- Matroid_oracle wikiPageWikiLink Polynomial-time_approximation_scheme.
- Matroid_oracle wikiPageWikiLink Polynomial_time.
- Matroid_oracle wikiPageWikiLink Regular_matroid.
- Matroid_oracle wikiPageWikiLink SIAM_Journal_on_Computing.
- Matroid_oracle wikiPageWikiLink SIAM_Journal_on_Discrete_Mathematics.
- Matroid_oracle wikiPageWikiLink Spanning_tree.
- Matroid_oracle wikiPageWikiLink Subroutine.
- Matroid_oracle wikiPageWikiLink Symmetric_group.
- Matroid_oracle wikiPageWikiLink Time_complexity.
- Matroid_oracle wikiPageWikiLink Transversal_matroid.
- Matroid_oracle wikiPageWikiLink Turing_reduction.
- Matroid_oracle wikiPageWikiLink Tutte_polynomial.
- Matroid_oracle wikiPageWikiLink Undirected_graph.
- Matroid_oracle wikiPageWikiLink Uniform_matroid.
- Matroid_oracle wikiPageWikiLink Upper_and_lower_bounds.
- Matroid_oracle wikiPageWikiLink Vector_space.
- Matroid_oracle wikiPageWikiLink Weighted_matroid.
- Matroid_oracle wikiPageWikiLinkText "Matroid oracle".
- Matroid_oracle wikiPageWikiLinkText "Rank oracle".
- Matroid_oracle wikiPageWikiLinkText "independence oracle".
- Matroid_oracle wikiPageWikiLinkText "matroid oracle".
- Matroid_oracle hasPhotoCollection Matroid_oracle.
- Matroid_oracle wikiPageUsesTemplate Template:Citation.
- Matroid_oracle wikiPageUsesTemplate Template:Harvnb.
- Matroid_oracle wikiPageUsesTemplate Template:Harvtxt.
- Matroid_oracle wikiPageUsesTemplate Template:Refbegin.
- Matroid_oracle wikiPageUsesTemplate Template:Refend.
- Matroid_oracle wikiPageUsesTemplate Template:Reflist.
- Matroid_oracle subject Category:Matroid_theory.
- Matroid_oracle hypernym Subroutine.
- Matroid_oracle type Article.
- Matroid_oracle type Article.
- Matroid_oracle type Combinatoric.
- Matroid_oracle comment "In mathematics and computer science, a matroid oracle is a subroutine through which an algorithm may access a matroid, an abstract combinatorial structure that can be used to describe the linear dependencies between vectors in a vector space or the spanning trees of a graph, among other applications.The most commonly used oracle of this type is an independence oracle, a subroutine for testing whether a set of matroid elements is independent.".
- Matroid_oracle label "Matroid oracle".
- Matroid_oracle sameAs m.0lqhzt4.
- Matroid_oracle sameAs Q6787905.
- Matroid_oracle sameAs Q6787905.
- Matroid_oracle wasDerivedFrom Matroid_oracle?oldid=675336619.
- Matroid_oracle isPrimaryTopicOf Matroid_oracle.