A greedy-algorithm characterization of valuated -matroids

DOI10.1016/0893-9659(91)90075-7MaRDI QIDQ1190645zbMATH OpenOpenAlexFDO

Authors Walter Wenzel, Andreas W. M. Dress

Publication date 26 September 1992

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

Full work available at URL https://doi.org/10.1016/0893-9659(91)90075-7

zbMATH Keywords

algorithmgreedy algorithmweight functionmatroids

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Recommendations

• Valuated matroids: A new look at the greedy algorithm
• Valuated matroids -- a new look at the greedy algorithm
• CHARACTERIZING A VALUATED DELTA-MATROID AS A FAMILY OF DELTA-MATROIDS*
• Two algorithms for valuated \(\Delta\)-matroids

Cites work

• scientific article; zbMATH DE number 4019084 (Why is no real title available?)
• scientific article; zbMATH DE number 4162893 (Why is no real title available?)
• Duality theory for finite and infinite matroids with coefficients
• Grassmann-Plücker relations and matroids with coefficients
• Greedy algorithm and symmetric matroids
• Optimal assignments in an ordered set: An application of matroid theory
• Some combinatorial properties of discriminants in metric vector spaces
• Valuated matroids: A new look at the greedy algorithm

Cited in

(29)

• Nonintersecting paths, Pfaffians, and -matroids
• An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach
• A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs
• A proof of Cunningham's conjecture on restricted subgraphs and jump systems
• A note on M-convex functions on jump systems
• Weakly greedy algorithm and pair-Delta-matroids
• Valuated matroids: A new look at the greedy algorithm
• Efficient optimal equation formulation in lumped power-conserving systems
• \(\Delta\)-matroids with the strong exchange conditions
• \(k\)-best solutions under distance constraints in valuated \(\Delta\)-matroids
• Well-layered maps and the maximum-degree k k-subdeterminant of a matrix of rational functions
• Well-layered maps---a class of greedily optimizable set functions
• Pfaffian forms and \(\Delta\)-matroids
• Optimal matching forests and valuated delta-matroids
• Induction of M-convex functions by linking systems
• Pfaffian forms and \(\Delta\)-matroids with coefficients
• Two algorithms for valuated \(\Delta\)-matroids
• Even factors, jump systems, and discrete convexity
• CHARACTERIZING A VALUATED DELTA-MATROID AS A FAMILY OF DELTA-MATROIDS*
• Hyperconvexity and tight-span theory for diversities
• On basic operations related to network induction of discrete convex functions
• Bisubmodular polyhedra, simplicial divisions, and discrete convexity
• Orthogonal matroids over tracts
• A `non-additive' characterization of \(\wp\)-adic norms.
• Valuated matroids -- a new look at the greedy algorithm
• A combinatorial formula for principal minors of a matrix with tree-metric exponents and its applications
• Note on exchange axioms for valuated matroids and valuated delta-matroids
• A survey of fundamental operations on discrete convex functions of various kinds
• Isotropical linear spaces and valuated Delta-matroids

This page was built for publication: A greedy-algorithm characterization of valuated \(\Delta\)-matroids

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