Matroid parity problem
id:
matroid-parity-problem-272-17796973
title:
Matroid parity problem
text:
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 Lawler (1976) 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 num
brand slug:
wiki
category slug:
encyclopedia
description:
Largest independent set of paired elements
original url:
https://en.wikipedia.org/wiki/Matroid_parity_problem
date created:
date modified:
2024-01-06T10:21:51Z
main entity:
{"identifier":"Q48999802","url":"https://www.wikidata.org/entity/Q48999802"}
image:
{"content_url":"https://upload.wikimedia.org/wikipedia/commons/f/fe/Graphic_matroid_parity.svg","width":324,"height":423}
fields total:
13
integrity:
15