About: Matroid oracle

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Matroid oracle Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon

http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FMatroid_oracle&invfp=IFP_OFF&sas=SAME_AS_OFF

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.

Attributes	Values
rdfs:label	Matroid oracle (en)
rdfs: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. (en)
dcterms:subject	Matroid theory Computation oracles
Wikipage page ID	36878315 (xsd:integer)
Wikipage revision ID	1124336234 (xsd:integer)
Link from a Wikipage to another Wikipage	Bicircular matroid Algorithm Matroid theory Undirected graph Vector space Double exponential function Ear decomposition Information Processing Letters Matching (graph theory) Matrix (mathematics) Oracle machine Weighted matroid Branch-decomposition SIAM Journal on Computing SIAM Journal on Discrete Mathematics Lower bound Function (computer programming) Combinatorica Computational complexity theory Empty set Parallel algorithm Spanning tree Matroid Matroid intersection Matroid minor Matroid rank Dual matroid Gammoid Linear independence Oriented matroid Field (mathematics) Discrete Mathematics (journal) Graphic matroid Journal of Combinatorial Theory Journal of Computer and System Sciences Circuit of a matroid Regular matroid Binary matroid Bipartite matroid Black box group Computation oracles Automorphism group Polynomial-time approximation scheme Greedy algorithm Group theory Polynomial time Implicit graph Independence system Indicator function Canadian Journal of Mathematics Tutte polynomial Eulerian matroid Symmetric group Turing reduction Uniform matroid P versus NP problem Mathematical Programming (journal) Boolean value Linear matroid Transversal matroid
Link from a Wikipage to an external page	http://www.utdallas.edu/~klaus/Mbook/matroiddecompositionbook.pdf http://cdm16009.contentdm.oclc.org/cdm/ref/collection/p13011coll6/id/66398
sameAs	Matroid oracle Matroid oracle Matroid oracle
dbp:wikiPageUsesTemplate	dbt:Citation dbt:Harvtxt dbt:Refbegin dbt:Refend dbt:Reflist dbt:Short_description dbt:Harvnb
has 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. (en)
gold:hypernym	Function (computer programming)
prov:wasDerivedFrom	wikipedia-en:Matroid_oracle?oldid=1124336234&ns=0
page length (characters) of wiki page	34003 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Matroid_oracle
is Link from a Wikipage to another Wikipage of	Ear decomposition Matroid parity problem Oracle machine Branch-decomposition Matroid Matroid intersection Matroid minor Matroid partitioning Matroid rank Dual matroid Graphic matroid Matroid girth Regular matroid Binary matroid Bipartite matroid Black box group Implicit graph

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 48 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software