مساله ی پیدا کردن یک گراف مخفی در بین تعدادی گراف ، learnin a hidden subgraph . این مقاله ای است که در کلاس در موردش صحبت کردم (حلی 4). دانلود
_ On the Power of Additive Combinatorial Search Model نوشته ی Grebinski در سال 1998: این مقاله در زمینه ی پیدا کردن بردار های مفخی (Recunstruction of hidden vector) و ساختن ماترس های جداکننده (Separating Martix ) با کمترین تعداد سطر است. با اینکه این مقاله تا حدی قدیمی است اما ایده های زیبایی دارد که خواندن آن را شدیدا توصیه می کنم. تکنیک هایی از قبیل روشهای احتمالاتی، کاربرد هایی از قضایای مانند مارکف و نگاه توپولوژیک به مسائل احتمالاتی در این مقاله دیده می شود.
مقاله ی Non-Adaptive Group Testing on graphs : در این مقاله یک الگوریتم non-adaptive برای پیدا کردن یک زیرگراف آلوده با m یال از یک گراف دلخواه n راسی است. نکته ی جالب اینکه این الگوریتم مستقل از تعداد یالهای گراف اصلی است و فقط به تعداد راسهای گراف اصلی و تعداد یالهای زیرگراف آلوده بستگی دارد.
