The complexity of the matroid-greedoid partition problem

DOI10.1016/j.tcs.2008.11.019zbMath1162.68016OpenAlexW2078439023MaRDI QIDQ1006060

Christopher Umans, Vera Asodi

Publication date: 17 March 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.11.019

zbMATH Keywords

matroidfixed-parameter complexitygreedoidextractor codesmatroid partition problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Similarity of binary relations based on rough set theory and topology: an application for topological structures of matroids ⋮ Matrix approach to spanning matroids of rough sets and its application to attribute reduction

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Greedoids
• The complexity of maximum matroid--greedoid intersection and weighted greedoid maximiza\-tion
• Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
• New Algorithms for Finding Irreducible Polynomials Over Finite Fields
• Simple extractors for all min-entropies and a new pseudorandom generator
• Extractor Codes
• Simple Constructions of Almost k-wise Independent Random Variables
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Extractors and pseudorandom generators
• Minimum partition of a matroid into independent subsets

This page was built for publication: The complexity of the matroid-greedoid partition problem