Least and most colored bases

DOI10.1016/J.DAM.2007.04.015zbMATH Open1124.05022OpenAlexW2125128537MaRDI QIDQ2381817FDOQ2381817

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

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

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)

Cites Work

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

Cited In (4)

• Labeled traveling salesman problems: complexity and approximation
• Approximate tradeoffs on weighted labeled matroids
• Approximation and hardness results for label cut and related problems
• 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)