Dada uma família de no máximo subconjuntos de . O fecho de união é uma outra família conjunto contendo cada conjunto que pode ser construído, tendo a união de 1 ou mais conjuntos em . Pordenotamos o número de conjuntos em . n { 1 , 2 , … , n } F C
Qual é a maneira mais rápida de calcular o fechamento da união?
Eu mostrei uma equivalência entre o fechamento da união e a lista de todos os conjuntos independentes máximos em um gráfico bipartido; portanto, sabemos que decidir o tamanho do fechamento da união é # P-completo.
No entanto, há uma forma de listar todos os conjuntos independentes máximas (ou cliques maximais) em tempo para um gráfico com nodos e arestas Tsukiyama et al. 1977. Mas isso não é especializado em gráficos bipartidos.
Demos um algoritmo para gráficos bipartidos com tempo de execução http://www.ii.uib.no/~martinv/Papers/BooleanWidth_I.pdf
Nosso método é baseado na observação de que qualquer elemento em pode ser produzido pela união de algum outro elemento de C e um dos conjuntos originais. Portanto, sempre que adicionarmos um elemento a C, tentaremos expandi-lo por um dos n conjuntos originais. Para cada um desses n ⋅ | C | define precisamos verificar se eles ainda estão em C . Armazenamos C como uma árvore de pesquisa binária, para que cada pesquisa faça log | C | ⋅ n tempo.
É possível encontrar o fechamento da união no tempo O ( | C | ⋅ n 2 ) ? Ou mesmo a tempo O ( | C | ⋅ n ) ?
fonte
Respostas:
A complexidade de enumerar conjuntos independentes máximos em gráficos é a mesma que em gráficos bipartidos; portanto, a bipartida não traz nada de novo.
fonte