edge-colored graphs

Minimum Color-Degree Perfect b -Matchings

  • Mariia Anapolska
  • Christina Büsing
  • Martin Comis
  • Tabea Brandt
    • Categories Dynamic Programming, Graphs and Matroids Tags , , , , ,

    The minimum color-degree perfect b-matching roblem (Col-BM) is a new extension of the perfect b-matching problem to edge-colored graphs. The objective of Col-BM is to minimize the maximum number of differently colored edges in a perfect b-matching that are incident to the same node. We show that Col-BM is NP-hard on bipartite graphs by a … Read more