Least and most colored bases

DOI10.1016/J.DAM.2007.04.015MaRDI QIDQ2381817zbMATHOpenAlexFDO

Authors Francesco Maffioli, Romeo Rizzi, Stefano Benati

Publication date 19 September 2007

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

Full work available at URL https://doi.org/10.1016/j.dam.2007.04.015

zbMATH Keywords

approximation algorithmsmatroid intersectionmatroidsminimum label spanning tree\(k\)-for-1 propertylow chromaticsMLST

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Recommendations

• A multiply constrained matroid optimization problem
• A matroid algorithm and its application to the efficient solution of two optimization problems on graphs
• Matroid optimization with generalized constraints
• On the minimum label spanning tree problem
• Algorithms and Data Structures for an Expanded Family of Matroid Intersection Problems

Cites work

• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• A note on the minimum label spanning tree.
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial optimization. Theory and algorithms.
• Matroids and the greedy algorithm
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• On the minimum label spanning tree problem
• Structure preserving reductions among convex optimization problems
• The minimum labeling spanning trees
• Wavelength rerouting in optical networks, or the Venetian Routing problem

Cited in

(4)

• Labeled traveling salesman problems: complexity and approximation
• Approximation and hardness results for label cut and related problems
• Approximate tradeoffs on weighted labeled matroids
• Algorithms and complexity for a class of combinatorial optimization problems with labelling

This page was built for publication: Least and most colored bases

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