An algorithmic characterization of antimatroids

DOI10.1016/0166-218X(90)90002-TzbMath0719.90063OpenAlexW1970429328WikidataQ56387982 ScholiaQ56387982MaRDI QIDQ2640448

Ulrich Faigle, E. Andrew Boyd

Publication date: 1990

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(90)90002-t

zbMATH Keywords

greedy algorithmprecedence constraintsjob schedulingalgorithmic characterizationminmax nesting problemtruncated antimatroids

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items

Critical sets, crowns and local maximum independent sets ⋮ A greedy algorithm for convex geometries ⋮ The forbidden minor characterization of line-search antimatroids of rooted digraphs ⋮ Antimatroids and balanced pairs ⋮ On the shelling antimatroids of split graphs ⋮ Characterizations of polygreedoids and poly-antimatroids by greedy algorithms ⋮ The affine representation theorem for abstract convex geometries ⋮ Recognition of Antimatroidal Point Sets ⋮ Finding a Maximum-Weight Convex Set in a Chordal Graph ⋮ A Geometric Characterization of Poly-antimatroids

Cites Work

• Homomorphisms and Ramsey properties of antimatroids
• The greedy algorithm for partially ordered sets
• Meet-distributive lattices and the anti-exchange closure
• Greedoids and Linear Objective Functions
• On ordered languages and the optimization of linear functions by greedy algorithms
• Introduction to Greedoids
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Optimal Sequencing of a Single Machine Subject to Precedence Constraints
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item