Saya (perlahan-lahan) menulis ulasan tentang Buku Pegangan Algoritma Chemoinformatika untuk SIGACT News. Satu bab membahas implementasi perangkat lunak saat ini, dan pencarian basis data (dan aplikasi lain) tampaknya tidak memanfaatkan sebanyak mungkin informasi tentang grafik. Di sisi lain, mungkin lebih banyak algoritma teoretis akan terlalu sulit untuk diterapkan. Sepertinya ini adalah area terbuka yang potensial.
Jadi inilah pertanyaan saya:
Apakah ada ikhtisar (atau sejumlah kecil referensi) yang membahas teori dan implementasi (mudah-mudahan) algoritma basis data grafik dengan informasi metrik? (Setiap tepi adalah jarak, dan setiap titik memiliki volume.) Deskripsi bebas kimia dari contoh masalah akan menjadi: diberi basis data grafik, temukan semuanya yang mengandung subgraph tertentu.
sumber
Jawaban:
Ini tampaknya terkait dengan masalah isomorfisma subgraph yang pada umumnya NP-lengkap, bahkan tanpa bobot. Artikel Wikipedia yang sesuai mengklaim bahwa itu dapat diselesaikan secara efisien dalam kasus-kasus tertentu.
Jika chemo- adalah sesuatu seperti bioinformatika, Anda mungkin akan tertarik pada algoritma aproksimasi untuk menangani noise. Juga, mengingat pencarian basis data sebagai aplikasi, mungkin ada ide-ide cerdas untuk preprocessing yang memberi Anda runtime diamortisasi yang baik.
Ditemukan (tidak dibaca) itu:
http://www.springerlink.com/content/4751121q3575v041/
http://bioinformatics.oxfordjournals.org/content/23/2/232.full
http://portal.acm.org/citation.cfm?id=1368898
Penafian : Sekali lagi, maaf untuk jawaban gaya komentar; Saya belum diizinkan berkomentar.
sumber