Fiquei me perguntando se a tarefa de procurar por três cores planares é de complexidade ou inferior? Parece que seria uma consequência intuitiva baseada nos resultados do separador planar; no entanto, na wikipedia , ele menciona apenas conjuntos independentes, árvores Steiner, ciclos hamiltonianos...
Estou trabalhando para tentar particionar um gráfico triangulado em subgráficos conectados com algumas garantias sobre o número de arestas entre partições. Aqui está um exemplo de um gráfico triangulado que foi particionado em 4 "clusters": O que eu queria originalmente era um algoritmo que...
O problema do subgráfico conectado de peso máximo é o seguinte: Entrada: um gráfico e um peso (possivelmente negativo) para cada vértice .w i i ∈ VG = ( V, E)G=(V,E)G=(V,E)WEuWEuw_ii ∈ VEu∈Vi \in V Saída: um subconjunto de peso máximo de vértices, de modo que esteja conectado.G [ S ]SSSG [...
Gostaria de saber se existe um algoritmo sublinear para excluir ou contrar uma aresta em uma incorporação combinatória de, digamos, gráfico planar? Como na incorporação combinatória, temos que manter os vértices de G e G * ao mesmo tempo, levando em consideração que a contração no primal é a...
Algum de vocês conhece uma referência para o seguinte resultado (surpreendentemente tedioso para provar)? Dado um gráfico plano conectado com n vértices e n + t arestas, ele possui um separador de vértices de tamanho O ( √GGGnnnn+tn+tn+t.O(t√+1)O(t+1)O(