Greedy algorithms and poset matroids

DOI10.1016/J.JDA.2014.07.005MaRDI QIDQ473210zbMATH OpenOpenAlexFDO

Authors L. Ferrari

Publication date 24 November 2014

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.3797

zbMATH Keywords

greedy algorithmmatroidposetabstract simplicial complex

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Nonnumerical algorithms (68W05) Combinatorial aspects of matroids and geometric lattices (05B35) Combinatorial aspects of simplicial complexes (05E45)

Abstract: We generalize the matroid-theoretic approach to greedy algorithms to the setting of poset matroids, in the sense of Barnabei, Nicoletti and Pezzoli (1998) [BNP]. We illustrate our result by providing a generalization of Kruskal algorithm (which finds a minimum spanning subtree of a weighted graph) to abstract simplicial complexes.

Recommendations

• A framework for the greedy algorithm
• scientific article; zbMATH DE number 3871387
• Greedy Families for Linear Objective Functions
• Introduction to Greedoids
• Valuated matroids -- a new look at the greedy algorithm

Cites work

• scientific article; zbMATH DE number 3742601 (Why is no real title available?)
• A THEOREM ON INDEPENDENCE RELATIONS
• A general model for matroids and the greedy algorithm
• Geometries on partially ordered sets
• Introduction to algorithms.
• Matroids and the greedy algorithm
• Matroids on partially ordered sets
• On ordered languages and the optimization of linear functions by greedy algorithms
• The greedy algorithm for partially ordered sets

Cited in

(3)

• Greedy-type resistance of combinatorial problems
• Generalized matroids based on three-way decision models
• scientific article; zbMATH DE number 3970766 (Why is no real title available?)

This page was built for publication: Greedy algorithms and poset matroids

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