Color constrained combinatorial optimization problems

DOI10.1016/0167-6377(91)90061-SMaRDI QIDQ1178732zbMATH OpenOpenAlexFDO

Authors Franz Rendl, Horst W. Hamacher

Publication date 26 June 1992

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(91)90061-s

zbMATH Keywords

polynomial algorithms3-matroid intersectioncolor constraintscolored bipartite matching

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• A multiply constrained matroid optimization problem
• Matroid optimization with generalized constraints
• Efficient algorithms for a family of matroid intersection problems
• Optimization problems with color-induced budget constraints
• Algorithms and Data Structures for an Expanded Family of Matroid Intersection Problems

Cites work

• scientific article; zbMATH DE number 3580570 (Why is no real title available?)
• A matroid algorithm and its application to the efficient solution of two optimization problems on graphs
• A multiply constrained matroid optimization problem
• A strongly polynomial minimum cost circulation algorithm
• Efficient algorithms for a family of matroid intersection problems
• Matroid optimization with the interleaving of two ordered sets
• Network flows. Theory, algorithms, and applications.
• Two algorithms for weighted matroid intersection
• k-Best constrained bases of a matroid

Cited in

(7)

• Budgeted colored matching problems
• Almost optimal solutions for bin coloring problems
• Algorithms and Computation
• The color-balanced spanning tree problem.
• A column-generation approach to the multiple knapsack problem with color constraints
• Biobjective optimization problems on matroids with binary costs
• On generalized balanced optimization problems

This page was built for publication: Color constrained combinatorial optimization problems

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