Matches in DBpedia 2016-04 for { <http://wikidata.dbpedia.org/resource/Q6787905> ?p ?o }
Showing triples 1 to 62 of
62
with 100 triples per page.
- Q6787905 subject Q8612141.
- Q6787905 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.".
- Q6787905 wikiPageExternalLink matroiddecompositionbook.pdf.
- Q6787905 wikiPageExternalLink 66398.
- Q6787905 wikiPageWikiLink Q1065144.
- Q6787905 wikiPageWikiLink Q1087987.
- Q6787905 wikiPageWikiLink Q1143357.
- Q6787905 wikiPageWikiLink Q125977.
- Q6787905 wikiPageWikiLink Q129239.
- Q6787905 wikiPageWikiLink Q13222616.
- Q6787905 wikiPageWikiLink Q1326518.
- Q6787905 wikiPageWikiLink Q141488.
- Q6787905 wikiPageWikiLink Q16155113.
- Q6787905 wikiPageWikiLink Q17011123.
- Q6787905 wikiPageWikiLink Q17086290.
- Q6787905 wikiPageWikiLink Q190109.
- Q6787905 wikiPageWikiLink Q190686.
- Q6787905 wikiPageWikiLink Q205084.
- Q6787905 wikiPageWikiLink Q226183.
- Q6787905 wikiPageWikiLink Q2393193.
- Q6787905 wikiPageWikiLink Q27670.
- Q6787905 wikiPageWikiLink Q2780987.
- Q6787905 wikiPageWikiLink Q2985068.
- Q6787905 wikiPageWikiLink Q3075235.
- Q6787905 wikiPageWikiLink Q3186905.
- Q6787905 wikiPageWikiLink Q371983.
- Q6787905 wikiPageWikiLink Q44337.
- Q6787905 wikiPageWikiLink Q4489310.
- Q6787905 wikiPageWikiLink Q4903641.
- Q6787905 wikiPageWikiLink Q4913901.
- Q6787905 wikiPageWikiLink Q4915411.
- Q6787905 wikiPageWikiLink Q4956329.
- Q6787905 wikiPageWikiLink Q504353.
- Q6787905 wikiPageWikiLink Q520777.
- Q6787905 wikiPageWikiLink Q5282038.
- Q6787905 wikiPageWikiLink Q5310216.
- Q6787905 wikiPageWikiLink Q5325632.
- Q6787905 wikiPageWikiLink Q5520354.
- Q6787905 wikiPageWikiLink Q5597156.
- Q6787905 wikiPageWikiLink Q6007291.
- Q6787905 wikiPageWikiLink Q6295014.
- Q6787905 wikiPageWikiLink Q6787903.
- Q6787905 wikiPageWikiLink Q6787908.
- Q6787905 wikiPageWikiLink Q6787909.
- Q6787905 wikiPageWikiLink Q7309609.
- Q6787905 wikiPageWikiLink Q7390256.
- Q6787905 wikiPageWikiLink Q7390263.
- Q6787905 wikiPageWikiLink Q746242.
- Q6787905 wikiPageWikiLink Q782566.
- Q6787905 wikiPageWikiLink Q7857002.
- Q6787905 wikiPageWikiLink Q7885108.
- Q6787905 wikiPageWikiLink Q7979897.
- Q6787905 wikiPageWikiLink Q831672.
- Q6787905 wikiPageWikiLink Q8366.
- Q6787905 wikiPageWikiLink Q843550.
- Q6787905 wikiPageWikiLink Q849512.
- Q6787905 wikiPageWikiLink Q8612141.
- Q6787905 wikiPageWikiLink Q874429.
- Q6787905 wikiPageWikiLink Q898572.
- Q6787905 wikiPageWikiLink Q948100.
- Q6787905 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.".
- Q6787905 label "Matroid oracle".