Couverture par sous-graphes bipartis complets
De Wikipedia, l'encyclopédie encyclopedia
En théorie des graphes, le problème de couverture minimum par sous-graphes bipartis complets (ou problème de couverture biclique) est un problème algorithmique qui consiste, étant donné un graphe, à trouver une famille minimale de sous-graphes bipartis complets couvrant ses arêtes[1], c'est-à-dire telle que chaque arête du graphe d'origine apparaisse dans au moins un sous-graphe de la couverture.
Le problème de décision associé au problème d'optimisation de couverture par au plus sous-graphes bipartis complets est NP-complet, et ce même si l'on se restreint à la couverture de graphes bipartis[2].