Encontrar aranhas

Existe um algoritmo de tempo polinomial para encontrar - se houver - uma aranha de abrangência de um determinado gráfico ? Uma aranha é uma árvore com no máximo um nó com grau maior que 2: eu sei que várias condições de grau em (essencialmente, graus de nó suficientemente grandes) garantem a existência de uma aranha de abrangência. Mas eu estou querendo saber se existe um algoritmo para arbitrário . Obrigado! $G$
insira a descrição da imagem aqui
$G$ $G$

ds.algorithms reference-request graph-theory graph-algorithms Joseph O'Rourke
fonte

O artigo “spanning spiders NP-complete” no Google mostrou uma versão do artigo de Gargano, Hammar, Hell, Stacho e Vaccaro 2004 como o primeiro resultado. A proposição 1 declara que está completa com NP. Isso responde sua pergunta?

Tsuyoshi Ito

G

$G$

G_{1}, G_{2}

$G_1,G_2$

v \in G

$v \in G$

e

$e$

v

$v$

H

$H$

e

$e$

Obrigado, Tsuyoshi & Chandra! Sim, isso responde à minha pergunta. Encontrei uma referência ao artigo de Gargano, mas não à NP-completude, e sim à condição suficiente para a existência de uma aranha-medidora.

Joseph O'Rourke

idealmente eles colocaram seus comentários como respostas :), mas a sua solução funciona tão bem

Suresh Venkat

@Suresh: Caso você não esteja ciente, eu não a publiquei como resposta, porque eu não achava que essa pergunta deveria ter sido feita aqui em primeiro lugar.

Tsuyoshi Ito

Encontrar aranhas

Respostas: