Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Matroid_oracle> ?p ?o. }
Showing items 1 to 14 of
14
with 100 items 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 66398.
- Matroid_oracle wikiPageExternalLink matroiddecompositionbook.pdf.
- Matroid_oracle wikiPageID "36878315".
- Matroid_oracle wikiPageRevisionID "574135683".
- Matroid_oracle hasPhotoCollection Matroid_oracle.
- Matroid_oracle subject Category:Matroid_theory.
- 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=574135683.
- Matroid_oracle isPrimaryTopicOf Matroid_oracle.