Generalized matroid matching
| Autor: | Jácint Szabó, András Recski |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Polynomial
Mathematics::Combinatorics Matching (graph theory) Generalization Applied Mathematics Existential quantification 0211 other engineering and technologies TheoryofComputation_GENERAL 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology 01 natural sciences Matroid Combinatorics 010201 computation theory & mathematics Parity problem Independent set ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION Discrete Mathematics and Combinatorics Time complexity Mathematics |
| Zdroj: | Discrete Applied Mathematics. 276:129-133 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2019.09.023 |
| Popis: | The matroid parity problem is known to be unsolvable in polynomial time in the general case and is polynomial for linearly represented matroids. Its generalization asks if there exists an independent set in a matroid, intersecting k-tuples in a given way. The known polynomial, non-polynomial and NP-hard special cases are summarized and some open cases are mentioned. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect