Eu sou muito novo na teoria dos grafos e estou tentandoentenda o seguinte. Dado um grafo não direcionado G com vértices V e bordas E, qual é a complexidade temporal da contagem de todos os subgráficos completos de tamanho k e qual a complexidade de tempo de contar todos os ciclos de comprimento k? Basicamente, qual é mais rápido? Estou apenas considerando casos em que k é par. Há alguma referência conhecida para isso?
Respostas:
0 para resposta № 1A contagem de todos os ciclos de comprimento k pode, em geral, ser obtida no tempo O (VE) (V = número de vértices, E = número de arestas), embora esse número possa ser muito melhorado dependendo de k (Ref). A contagem de todos os subgráficos ou cliques completos pode ser obtida em O (nk k2) no caso geral, mas, novamente, esse número pode ser melhorado dependendo da estrutura do gráfico e do algoritmo usado (Ref).