About: Matroid parity problem

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by as a common generalization of graph matching and matroid intersection. It is also known as polymatroid matching, or the matchoid problem. Matroid parity can be solved in polynomial time for linear matroids. However, it is NP-hard for certain compactly-represented matroids, and requires more than a polynomial number of steps in the matroid oracle model.

thumbnail
Property Value
dbo:abstract
  • In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by as a common generalization of graph matching and matroid intersection. It is also known as polymatroid matching, or the matchoid problem. Matroid parity can be solved in polynomial time for linear matroids. However, it is NP-hard for certain compactly-represented matroids, and requires more than a polynomial number of steps in the matroid oracle model. Applications of matroid parity algorithms include finding large planar subgraphs and finding graph embeddings of maximum genus. These algorithms can also be used to find connected dominating sets and feedback vertex sets in graphs of maximum degree three. (en)
dbo:thumbnail
dbo:wikiPageID
  • 56069479 (xsd:integer)
dbo:wikiPageLength
  • 20351 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1093774821 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
rdfs:comment
  • In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by as a common generalization of graph matching and matroid intersection. It is also known as polymatroid matching, or the matchoid problem. Matroid parity can be solved in polynomial time for linear matroids. However, it is NP-hard for certain compactly-represented matroids, and requires more than a polynomial number of steps in the matroid oracle model. (en)
rdfs:label
  • Matroid parity problem (en)
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License