Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/7973| Заглавие документа: | On the inapproximability of independent domination in 2P3-free perfect graphs |
| Авторы: | Orlovich, Yu. L. Gordon, Valery S. Werrac, Dominique |
| Тема: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика |
| Дата публикации: | 2009 |
| Библиографическое описание источника: | Orlovich, Yury L. On the inapproximability of independent domination in 2P3-free perfect graphs / Y.Orlovich, V.Gordon, D.Werra // Theoretical Computer Science. - 2009. - №410. - P. 977–982. |
| Аннотация: | We consider the complexity of approximation for the Independent Dominating Set problem in 2P3-free graphs, i.e., graphs that do not contain two disjoint copies of the chordless path on three vertices as an induced subgraph. We show that, if P 6D NP, the problem cannot be approximated for 2P3-free graphs in polynomial time within a factor of n1" for any constant " > 0, where n is the number of vertices in the graph. Moreover, we show that the result holds even if the 2P3-free graph is restricted to being weakly chordal (and thereby perfect). |
| URI документа: | http://elib.bsu.by/handle/123456789/7973 |
| Располагается в коллекциях: | Статьи факультета прикладной математики и информатики |
Полный текст документа:
| Файл | Описание | Размер | Формат | |
|---|---|---|---|---|
| inapproximability.pdf | 566,32 kB | Adobe PDF | Открыть |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.