Estou procurando um algoritmo rápido para calcular o fluxo máximo em gráficos dinâmicos. ou seja, dado um gráfico e , temos o fluxo máximo em de para . Em seguida, novos / antigo nó adicionado / eliminadas com as suas arestas correspondentes de modo a formar um gráfico . O que é um fluxo máximo no...
Houve alguns esforços para atacar o problema do isomorfismo de grafos usando a caminhada aleatória quântica de bósons do núcleo duro (simétrica, mas sem ocupação dupla). O poder simétrico da matriz de adjacência, que parecia promissor, mostrou-se incompleto para gráficos gerais neste artigo por...
Digamos que um gráfico tenha a propriedade M se seus vértices puderem ser ordenados v 1 , v 2 , … v n de maneira que o gráfico H i induzido pelos vértices { v 1 , … , v i } tenha d i s t H i ( v j , v k ) = d i s t G ( v j , vGGGMMMv1,v2,…vnv1,v2,…vnv_1, v_2, \ldots
Estou procurando um pequeno gráfico GGG cujo número cromático vetorial é menor que o número cromático,
Eu quero ser muito específico. Alguém sabe de uma reprovação ou de uma prova da seguinte proposição: ∃p∈Z[x],n,k,C∈N,∃p∈Z[x],n,k,C∈N,\exists p \in \mathbb{Z}[x], n, k, C \in \mathbb{N}, ∀G,H∈STRUC[Σgraph](min(|G|,|H|)=n,G≄H),∀G,H∈STRUC[Σgraph](min(|G|,|H|)=n,G≄H),\forall G, H \in...
Eu tenho parte de uma tentativa de prova de . A tentativa prova consiste numa redução do Karp problema -completo cobertura de vértices 3-regular para sab.⊕P⊆NP⊕P⊆NP\oplus \mathbf{P} \subseteq \mathbf{NP}⊕P⊕P\oplus \mathbf{P}⊕⊕\oplus Dado um gráfico cúbico , a redução gera uma fórmula CNF com as...
Dado um gráfico direcionado com n nós, de modo que cada vértice tenha exatamente duas arestas de saída e um número natural N codificado em binário, dois vértices s e t, Quero contar o número de caminhos (não necessariamente simples) de s a t em N etapas. Este é um problema # P-difícil? Ou,...
Sabemos, por exemplo, de Koutis-Miller-Peng (baseado no trabalho de Spielman & Teng), que podemos resolver muito rapidamente sistemas lineares Ax=bAx=bA x = b para matrizes AAA que são o gráfico da matriz laplaciana para algum gráfico esparso com pesos de borda não negativos . Agora (primeira...
Aqui: http://www.planarity.org/Klein_elementary_graph_theory.pdf (em captações de capítulos) é dada uma definição de incorporação combinatória de um gráfico planar. (com definição de faces e assim por diante) Embora possa ser facilmente usado para qualquer gráfico, eles definem o gráfico planar...
Em um gráfico direcionado, , , se é um DAG (gráfico acíclico direcionado), é chamado de conjunto de arco de feedback. F ⊂ E G ∖ F FG = ( V, E)G=(V,E)G=(V,E)F⊂ EF⊂EF\subset EG ∖ FG∖FG\setminus FFFF Se cada aresta estiver associada a um peso , o problema do conjunto de arcos de feedback de custo...
Isso pode parecer mais uma questão de ciências sociais do que uma questão do TCS, mas não é. Ao ler " Algoritmos aleatórios ", que descrevem o problema do casamento estável, pode-se ler o seguinte (p54) "Pode-se demonstrar que, para todas as listas de preferências, existe pelo menos um casamento...
Gostaria de perguntar se já existe um resultado publicado sobre isso: Pegamos todos os caminhos diferentes possíveis entre cada par de nós de dois gráficos regulares conectados (com grau , digamos, e número de nós n ) e anotamos seus comprimentos. Claro que esse número de caminhos distintos é...
Gostaria de saber se o seguinte problema pode ser decidido em (logspace nondeterministic):N LNL\mathsf{NL} Dado um gráfico direcionado com dois vértices distintos s e t , existe um caminho único de s para t em G ?GGGssstttssstttGGG Eu sinto que é provável que seja em , uma vez que pode decidir...
Suponha que tenhamos um semigrupo com os elementos S = { s 1 , s 2 , … , s n } . Nosso objetivo é produtos de computação s i ∘ s i + 1 ∘ ⋯ ∘ s j .(S,∘)(S,∘)(S,\circ)S={s1,s2,…,sn}S={s1,s2,…,sn}S=\lbrace s_1,s_2,\dots,s_n\rbracesi∘si+1∘⋯∘sjsi∘si+1∘⋯∘sjs_i\circ s_{i+1}\circ \cdots\circ s_j Em seu...
Isso me confunde. Um caso fácil de contagem é quando o problema de decisão está em e não há soluções.PPP Uma palestra mostra que o problema de contar o número de combinações perfeitas em um gráfico bipartido (equivalente a contar o número de capas de ciclo em um gráfico direcionado) é completo.#...
Dado um gráfico com arestas ponderadas, como podemos encontrar um ciclo negativo que contenha pelo menos um vértice em um determinado conjunto de vértices ? Obrigado.{V1,V2,…,Vk}{V1,V2,…,Vk}\{V_1, V_2, \ldots,
Estou procurando uma maneira de gerar gráficos para que a cobertura ideal do vértice seja conhecida. Não há restrições quanto ao número de nós ou arestas, apenas que o gráfico esteja completamente conectado. a idéia é gerar um gráfico que não seja fácil de encontrar a cobertura ideal de vértice,...
Recordar o diâmetro de um gráfico que é o comprimento de um caminho mais longo que mais curto em . Dado um gráfico, um algoritmo óbvio para calcular resolve o problema de caminho mais curto de todos os pares (APSP) e retorna o comprimento do caminho mais longo encontrado.G diam ( G )GGGGGGdiam ( G...
O teorema de Courcelle afirma que toda propriedade de gráfico definível na lógica monádica de segunda ordem pode ser decidida em tempo linear em gráficos de largura de árvore limitada . Este é um dos meta-teoremas algorítmicos mais conhecidos. Motivado pelo teorema de Courcelle, fiz a seguinte...
O que se sabe atualmente sobre a aproximabilidade do problema de gênero? A pesquisa preliminar me diz que um fator de aproximação constante é trivial para gráficos suficientemente densas, e um nϵnϵn^\epsilon -approximation algoritmo foi descartada. Essas informações estão atualizadas ou existem...