Budgeted colored matching problems

DOI10.1016/J.ENDM.2018.01.026MaRDI QIDQ1742233zbMATH OpenOpenAlexWikidataFDO

Authors Christina Büsing, Martin Comis

Publication date 11 April 2018

Full work available at URL https://doi.org/10.1016/j.endm.2018.01.026

zbMATH Keywords

complexitybudgeted optimizationbudgeted matching

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Dynamic programming (90C39) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• On some matching problems under the color-spanning model
• Optimization problems with color-induced budget constraints
• Optimization problems with color-induced budget constraints
• Approximation Algorithms for Bounded Color Matchings via Convex Decompositions
• Color constrained combinatorial optimization problems
• Multi-budgeted matching problems
• On the fixed-parameter tractability of some matching problems under the color-spanning model
• The Budgeted Unique Coverage Problem and Color-Coding
• Structural parameterizations of budgeted graph coloring
• Structural parameterizations of budgeted graph coloring

Cites work

• Approximation Schemes for Multi-Budgeted Independence Systems
• Budgeted matching and budgeted matroid intersection via the gasoline puzzle
• Exact arborescences, matchings and cycles
• Multi-budgeted matchings and matroid intersection via dependent rounding
• Paths, trees and matchings under disjunctive constraints
• Random pseudo-polynomial algorithms for exact matroid problems
• Some Matching Problems for Bipartite Graphs
• The Recognition of Series Parallel Digraphs
• The budgeted minimum cost flow problem with unit upgrading cost
• Utilitarian mechanism design for multiobjective optimization

Cited in

(4)

• Structural parameterizations of budgeted graph coloring
• Multi-budgeted matching problems
• Minimum <scp>color‐degree</scp> perfect b‐matchings
• Integrality gaps for colorful matchings

This page was built for publication: Budgeted colored matching problems

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