Trouver des araignées étendues

Existe-t-il un algorithme polynomial pour trouver, s'il en existe un, une araignée s'étendant sur un graphe donné ? Une araignée est un arbre avec au plus un nœud avec un degré supérieur à 2: je sais que diverses conditions de degré sur (essentiellement, des degrés de nœud suffisamment grands) garantissent l'existence d'une araignée s'étendant. Mais je me demande s'il existe un algorithme pour arbitraire . Merci! $G$
entrez la description de l'image ici
$G$ $G$

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

La recherche «Spanning Spiders NP-complete» sur Google a montré le premier résultat d' une version de l'article de Gargano, Hammar, Hell, Stacho et Vaccaro 2004 . La proposition 1 indique qu'elle est NP-complète. Est-ce que cela répond à votre question?

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$

Merci, Tsuyoshi & Chandra! Oui, cela répond à ma question. J'ai rencontré une référence au papier Gargano mais pas pour l'exhaustivité de NP, plutôt pour leur condition suffisante pour l'existence d'une araignée couvrante.

Joseph O'Rourke

idéalement, ils auraient posté leurs commentaires comme réponses :), mais votre solution fonctionne aussi

Suresh Venkat

@Suresh: Au cas où vous ne seriez pas au courant, je ne l'ai pas posté comme réponse car je ne pensais pas que cette question aurait dû être posée ici en premier lieu.

Tsuyoshi Ito

Trouver des araignées étendues

Réponses: