Is there an optimal solution for this bipartite graph coloring problem?

Revision en1, by Silence_for_Melody, 2017-06-18 21:45:57

Hi, I would like to know if there is some algorithm to solve the following problem, or maybe it is NP.

Given a bipartite graph of at most 200 nodes in each side, I need to color the minimum number of nodes so each node is colored or has a colored neighbor. The colored nodes could be in any side.

Thanks for your answers.

Tags bipartite, colorings

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Silence_for_Melody 2017-06-18 21:45:57 398 Initial revision (published)