Una soluzione esatta per il problema della copertura del vertice Biclique su un grafico bipartito
-
05-11-2019 - |
Domanda
Il problema della copertura del vertice biclique chiede se il set di vertice del grafico dato può essere coperto con il massimo da "K" bicliques (sottogruppi bipartiti completi).
È stato dimostrato che la "copertura del vertice biclique" non è un trattabile a parametro fisso a meno che p = np in Copertura di grafici con pochi sottografici bipartiti completi.
La maggior parte del lavoro in letteratura ha dimostrato la durezza del problema in casi generali/speciali. Tuttavia, Ho bisogno di un algoritmo esatto per risolvere questo problema sui grafici bipartiti. Un algoritmo approssimativo con una garanzia è anche buono (sono a conoscenza "Clustering e il problema della partizione Biclique", Ma ha fornito una soluzione approssimativa per" Biclique Vertex Partition "non copertura vertice, cioè la soluzione fornita è per i bicliques disgiunti non eventualmente sovrapposti).
Qualcuno è a conoscenza di un algoritmo esatto per il problema "Biclique Vertex-Cover"? Potenzialmente, con l'analisi della complessità del tempo?
Un algoritmo ingenuo, forse, inizierebbe dall'intero grafico bipartito per verificare una biclique che copre tutti i vertici (che coprono con una biclique). Se non è riuscito, controlliamo i sottoinsiemi rimuovendo un vertice e indaghiamo se esistono due biclique in questo set che coprono tutti i vertici (cercando di coprire due bicliques) e così via (cercando di coprire più biclique fino a raggiungere "k") .
Nessuna soluzione corretta