Algoritmos y complejidad computacional de cubiertas de camarillas y bicliques

He estado leyendo un artículo de un químico matemático. Propone algunos índices para medir la complejidad de las moléculas. De aquí en adelante, en lugar de moléculas, piense en gráficos conectados no dirigidos: un vértice es un átomo y un borde es un enlace entre los átomos. Es posible considerar los colores de los vértices, distinguir los Nitrógenos aparte de los Carbones, por ejemplo, pero ignoraré esa parte por ahora.

El punto: los índices que sugiere están motivados por la heurística y la experimentalidad "se ve bien hasta ahora". Creo que debe haber alguna teoría real sobre algunas de estas cantidades, y espero obtener algunos consejos aquí.

Fijar un gráfico . Deje y dos tapas de . Digamos que y son el mismo tipo de cobertura si contienen los mismos tipos de subgráficos en números iguales. (Nota y no tienen que ser isomórficas). Ahora definimos las siguientes cantidades: $G$ $C$ $C'$ $G$ $C$ $C'$ $C$ $C'$

$k_S(G) =$ número de tipos de cubiertas de camarilla de borde mínimo de número total de cubiertas de camarilla de borde mínimo de igual que pero para bicliques igual que pero para bicliques número de tipos de particiones de los bordes de en camarillas número total de particiones de los bordes del gráfico en camarillas como arriba, pero con particiones de en bicliques $G$
$k_T(G) =$ $G$
$k^{bi}_S(G) =$ $k_S(G)$
$k^{bi}_T(G) =$ $k_T(G)$
$p_S(G) =$ $G$
$p_T(G) =$
$p^{bi}_S(G), p^{bi}_T(G)$ $G$

Empíricamente, aparentemente es más fácil calcular las medidas que calcular las medidas . Espero que se deba saber algo sobre el cálculo de algunas de estas cantidades. ¿Alguien puede proporcionar algoritmos, dureza computacional, etc.? Gracias. $p$ $k$

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

¿Son estos gráficos de una clase restringida? Quiero decir, ¿quieres algoritmos para estas medidas en gráficos arbitrarios o solo aquellos que surgen en la química? Si no está buscando algoritmos generales, puede ser útil establecer las propiedades de los gráficos que surgen en química para encontrar una respuesta a su pregunta.

Kaveh

"Empíricamente, aparentemente es más fácil calcular las medidas p que calcular las medidas k". Supongo que "más fácil" significa que el cálculo es más rápido (en lugar de, por ejemplo, que el algoritmo es fácil de describir). Si este es el caso, ¿de qué tipo de algoritmos estás hablando? Si está enumerando todas las posibilidades mediante retroceso o por algún otro método, las medidas p son menores que las medidas k correspondientes, lo que significa que puede no ser sorprendente que las medidas p sean más rápidas de calcular.

Tsuyoshi Ito

Algoritmos y complejidad computacional de cubiertas de camarillas y bicliques

Respuestas: