Algoritmos e complexidade computacional de capas de clique e biclique

Eu tenho lido um artigo de um químico matemático. Ele propõe alguns índices para medir a complexidade das moléculas. A partir daqui, em vez de moléculas, pense em gráficos conectados não direcionados: um vértice é um átomo e uma aresta é uma ligação entre átomos. É possível considerar a coloração dos vértices, diferenciar os nitrogênios dos carbonos, por exemplo, mas ignorarei essa parte por enquanto.

O ponto: os índices que ele sugere são motivados pela heurística e experimental "parece bom até agora". Eu acho que deve haver alguma teoria real conhecida sobre algumas dessas quantidades, e espero obter algumas dicas aqui.

Fixar um gráfico . Vamos e ser duas capas de . Digamos que e sejam o mesmo tipo de capa se contiverem os mesmos tipos de subgráficos em números iguais. (As notas e não precisam ser isomórficas.) Agora, definimos as seguintes quantidades: $G$ $C$ $C'$ $G$ $C$ $C'$ $C$ $C'$

número de tipos de coberturas mínimas de bordas de borda de número total de coberturas mínimas de bordas de bordas de igual a mas para bicliques igual a mas para bicliques $k_S(G) =$ $G$
$k_T(G) =$ $G$
$k^{bi}_S(G) =$ $k_S(G)$
$k^{bi}_T(G) =$ $k_T(G)$
número de tipos de partições das arestas de em cliques número total de partições das arestas do gráfico em cliques como acima, mas com partições de em bicliques $p_S(G) =$ $G$
$p_T(G) =$
$p^{bi}_S(G), p^{bi}_T(G)$ $G$

Empiricamente, é aparentemente mais fácil calcular as medidas do que calcular as medidas . Espero que algo deva ser conhecido em algum lugar sobre o cálculo de algumas dessas quantidades. Alguém pode fornecer algoritmos, dureza computacional etc.? Obrigado. $p$ $k$

cc.complexity-theory ds.algorithms graph-algorithms clique Aaron Sterling
fonte

Esses gráficos são de uma classe restrita? Quero dizer, você quer algoritmos para essas medidas em gráficos arbitrários ou apenas aqueles que surgem na química? Se você não está procurando algoritmos gerais, a indicação das propriedades dos gráficos resultantes da química pode ser útil para encontrar uma resposta para sua pergunta.

Kaveh

"Empiricamente, é aparentemente mais fácil calcular as medidas p do que calcular as medidas k." Suponho que "mais fácil" significa que o cálculo é mais rápido (em vez de, digamos, que o algoritmo seja fácil de descrever). Se for esse o caso, de que tipo de algoritmos você está falando? Se você estiver enumerando todas as possibilidades pelo retorno ou por outro método, as medidas p são menores que as medidas k correspondentes, o que significa que pode não ser surpreendente que as medidas p sejam mais rápidas de calcular.

Tsuyoshi Ito

Algoritmos e complexidade computacional de capas de clique e biclique

Respostas: