The computational complexity of antimatroid properties

DOI10.1006/AAMA.2000.0704MaRDI QIDQ5933438zbMATH OpenOpenAlexFDO

Authors Jamas Enright

Publication date 16 May 2001

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/aama.2000.0704

zbMATH Keywords

oracle complexity for antimatroids

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 4191655
• scientific article; zbMATH DE number 512933
• Antimatroids of finite character
• Matroid Complexity and Nonsuccinct Descriptions
• An algorithmic characterization of antimatroids

Cites work

• Greedoids
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 4137538 (Why is no real title available?)
• scientific article; zbMATH DE number 1185289 (Why is no real title available?)
• scientific article; zbMATH DE number 3723844 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• Introduction to Greedoids
• Matching theory
• Recognizing graphic matroids
• The computational complexity of matroid properties

Cited in

(5)

• A representation of antimatroids by Horn rules and its application to educational systems
• An algorithmic characterization of antimatroids
• Resolutions of convex geometries
• Complexity of Computing the Anti-Ramsey Numbers for Paths.
• Mathematical characterizations and computational complexity of anti-slide puzzles

This page was built for publication: The computational complexity of antimatroid properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5933438)