Algoritma optimal untuk menemukan ketebalan grafik tipis?

Saya bertanya-tanya bagaimana menemukan ketebalan grafik tidak berarah jarang. Maksud saya, jarang . Maksud saya adalah kompleksitas waktu terendah. $|E|=O(|V|)$

Saya memikirkan beberapa modifikasi pada algoritma Tarjan untuk grafik yang tidak diarahkan, tetapi saya tidak menemukan hasil yang baik. Sebenarnya saya berpikir bahwa jika saya dapat menemukan 2 komponen yang terhubung di , maka saya dapat menemukan ketebalannya, dengan semacam induksi yang dapat dicapai dari bagian pertama. Saya mungkin berada di jalur yang salah. Algoritma apa saja asimtotik lebih baik dari (yaitu ) diterima. $O(|V|)$ $\Theta(|V|^2)$ $o(|V|^2)$

Ini mungkin masih merupakan masalah terbuka dan mungkin lebih cocok untuk sejarah.

Aryabhata

Tetapi akan pantas untuk bertanya pada cstheory apakah ini masalah terbuka.

JeffE

@ Suresh, saya tidak bisa berpikir lebih baik daripada untuk BFS. Juga jika ini cocok untuk CStheory saya akan menanyakannya di sana besok.

Ω (n^{2})

$\Omega(n^2)$

Catatan: pertanyaan ini telah ditransfer ke cstheory. Voting untuk ditutup.

Suresh

@ Suresh: Daripada menutup, kita hanya perlu menambahkan jawaban di sini dengan tautan ke jawaban di sana, dengan mengatakan itu dijawab dalam cstheory. Selain itu, apa yang akan kita tutup? Diluar topic? (Saya telah menambahkan jawaban CW).

Aryabhata

Jawaban:

Lihat Algoritme optimal untuk menemukan ketebalan grafik tipis dari cstheory.SE yang memiliki jawaban yang diterima.

Aryabhata
sumber

Saya pikir jawaban di CSTheory belum lengkap, saya menunggu referensi lagi jadi saya belum menandainya sebagai jawaban. Tapi di sini Anda dapat memutuskan untuk menutup ini, tetapi saya tidak akan menghapusnya karena saya pikir ada baiknya memiliki riwayat masalah ini di CS. PS: Saya tahu Shiva sangat bagus di bidang terkait, tapi tetap saya pikir lebih baik membiarkannya terbuka, mungkin orang lain punya referensi yang lebih baik.

@ SaeedAmiri: Anda mungkin tidak selalu menemukan referensi. Ada kemungkinan bahwa tidak ada yang mempertimbangkan masalah ini sebelumnya, atau membuat catatan eksplisit di beberapa daftar masalah terbuka. Anda selalu dapat membiarkan pertanyaan Anda tidak ditandai. btw, saya menentang menutupnya di sini. Ini adalah pertanyaan yang benar-benar valid untuk situs ini, dan menutupnya mungkin memberikan kesan yang salah untuk penanya di masa depan.

Aryabhata

lihatlah pertanyaan cstheory sekarang.

Suresh

Lihat juga Kuliah tentang Siklus dalam Grafik .

Pål GD