Menemukan laba-laba yang merentang

10

Apakah ada algoritma waktu polinomial untuk menemukan — jika ada — laba-laba spanning dari suatu graf ? Laba-laba adalah pohon dengan paling banyak satu simpul dengan derajat lebih besar dari 2: Saya tahu bahwa berbagai kondisi derajat pada G (pada dasarnya, derajat simpul cukup besar) menjamin keberadaan laba-laba yang merentang. Tapi saya bertanya-tanya apakah ada algoritma untuk G sewenang-wenang . Terima kasih!G
          masukkan deskripsi gambar di sini
GG

Joseph O'Rourke
sumber
9
Googling "spanning spider NP-complete" menunjukkan versi artikel oleh Gargano, Hammar, Hell, Stacho, dan Vaccaro 2004 sebagai hasil pertama. Proposisi 1 menyatakan bahwa NP-complete. Apakah ini menjawab pertanyaan Anda?
Tsuyoshi Ito
13
GG1,G2vGevHe
1
Terima kasih, Tsuyoshi & Chandra! Ya, itu menjawab pertanyaan saya. Saya menemukan referensi ke kertas Gargano tetapi tidak untuk kelengkapan NP, melainkan karena kondisi mereka yang cukup untuk keberadaan laba-laba yang merentang.
Joseph O'Rourke
1
idealnya mereka akan memposting komentar mereka sebagai jawaban :), tetapi solusi Anda juga berfungsi
Suresh Venkat
@ Suresh: Jika Anda tidak sadar, saya tidak mempostingnya sebagai jawaban karena saya tidak berpikir bahwa pertanyaan ini seharusnya ditanyakan di sini sejak awal.
Tsuyoshi Ito

Jawaban:

4

Pertanyaan telah dijawab dalam komentar oleh Tsuyoshi & Chandra! Saya menambahkan jawaban CW ini sehingga saya dapat menerimanya untuk menunjukkan bahwa pertanyaan sudah ditutup. Terimakasih semuanya!

Joseph O'Rourke
sumber
1
IIRC Anda harus menunggu 2 hari setelah memposting pertanyaan untuk menerima jawaban Anda sendiri.
Kaveh