RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискретн. анализ и исслед. опер., сер. 1, 1999, том 6, номер 4, страницы 3–19 (Mi da324)  

Эта публикация цитируется в 25 научных статьях (всего в 25 статьях)

Полиномиальный алгоритм для нахождения наибольших независимых множеств в графах без вилок

В. Е. Алексеев

Нижегородский государственный университет им. Н. И. Лобачевского

Аннотация: Вилка – это граф, получаемый из звезды $K_{1,3}$ подразбиением одного ребра. Известно [6-8], что для графов без звезд задача нахождения наибольшего независимого множества решается за полиномиальное время. Доказывается, что это верно и для более широкого класса графов без вилок. Библиогр. 9.

Полный текст: PDF файл (2217 kB)

Реферативные базы данных:
УДК: 519.17
Статья поступила: 14.01.1999
Переработанный вариант: 19.07.1999

Образец цитирования: В. Е. Алексеев, “Полиномиальный алгоритм для нахождения наибольших независимых множеств в графах без вилок”, Дискретн. анализ и исслед. опер., сер. 1, 6:4 (1999), 3–19

Цитирование в формате AMSBIB
\RBibitem{Ale99}
\by В.~Е.~Алексеев
\paper Полиномиальный алгоритм для нахождения наибольших независимых множеств в~графах без вилок
\jour Дискретн. анализ и исслед. опер., сер.~1
\yr 1999
\vol 6
\issue 4
\pages 3--19
\mathnet{http://mi.mathnet.ru/da324}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1760726}
\zmath{https://zbmath.org/?q=an:0931.05078}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da324
  • http://mi.mathnet.ru/rus/da/v6/s1/i4/p3

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Lozin V.V., “Bipartite graphs without a skew star”, Discrete Math, 257:1 (2002), 83–100  crossref  mathscinet  zmath  isi  scopus
    2. Alekseev V.E., “On easy and hard hereditary classes of graphs with respect to the independent set problem”, Discrete Appl Math, 132:1–3 (2003), 17–26  crossref  mathscinet  zmath  isi  scopus
    3. Alexe G., Hammer P.L., Lozin V.V., de Werra D., “Struction revisited”, Discrete Appl Math, 132:1–3 (2003), 27–46  crossref  mathscinet  zmath  isi  scopus
    4. Brandstadt A., Mosca R., “On the structure and stability number Of P-5- and co-chair-free graphs”, Discrete Appl Math, 132:1–3 (2003), 47–65  crossref  mathscinet  zmath  isi  scopus
    5. Gerber M.U., Hertz A., Schindl D., “P-5-free augmenting graphs and the maximum stable set problem”, Discrete Appl Math, 132:1–3 (2003), 109–119  crossref  mathscinet  zmath  isi  scopus
    6. Gerber M.U., Hertz A., Lozin V.V., “Stable sets in two subclasses of banner-free graphs”, Discrete Appl Math, 132:1–3 (2003), 121–136  crossref  mathscinet  zmath  isi  scopus
    7. Mosca R., “Some results on maximum stable sets in certain P-5-free graphs”, Discrete Appl Math, 132:1–3 (2003), 175–183  crossref  mathscinet  zmath  isi  scopus
    8. Boliac R., Lozin V.V., “An augmenting graph approach to the stable set problem in P-5-free graphs”, Discrete Appl Math, 131:3 (2003), 567–575  crossref  mathscinet  zmath  isi  scopus
    9. Brandstadt A., Hoang C.T., Le V.B., “Stability number of bull- and chair-free graphs revisited”, Discrete Appl Math, 131:1 (2003), 39–50  crossref  mathscinet  zmath  isi  scopus
    10. Hertz A., Lozin V., Schindl D., “Finding augmenting chains in extensions of claw-free graphs”, Inform Process Lett, 86:6 (2003), 311–316  crossref  mathscinet  zmath  isi  scopus
    11. Gerber M.U., Lozin V.V., “On the stable set problem in special P-5-free graphs”, Discrete Appl Math, 125:2–3 (2003), 215–224  crossref  mathscinet  zmath  isi  scopus
    12. Alekseev V.E., Lozin V.V., “Augmenting graphs for independent sets”, Discrete Appl Math, 145:1 (2004), 3–10  crossref  mathscinet  zmath  isi  scopus
    13. Brandstadt A., Le V.B., De Ridder H.N., “Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes”, Inform Process Lett, 89:4 (2004), 165–173  crossref  mathscinet  zmath  isi  scopus
    14. Zverovich I.E., Zverovich I.I., “Penta-extensions of hereditary classes of graphs”, J Comb Optim, 10:2 (2005), 169–178  crossref  mathscinet  zmath  isi  scopus
    15. Gerber M.U., Hertz A., Lozin V.V., “Augmenting chains in graphs without a skew star”, Journal of Combinatorial Theory Series B, 96:3 (2006), 352–366  crossref  mathscinet  zmath  isi  scopus
    16. Hougardy S., “Classes of perfect graphs”, Discrete Math, 306:19–20 (2006), 2529–2571  crossref  mathscinet  zmath  isi  elib  scopus
    17. Mosca R., “Stable sets of maximum weight in (P-7, banner)-free graphs”, Discrete Math, 308:1 (2008), 20–33  crossref  mathscinet  zmath  isi  elib  scopus
    18. Mosca R., “Some observations on maximum weight stable sets in certain P-5-free graphs”, European J Oper Res, 184:3 (2008), 849–859  crossref  mathscinet  zmath  isi  elib  scopus
    19. Mosca R., “Some Results on Stable Sets for K-Colorable P-6-Free Graphs and Generalizations”, Discret. Math. Theor. Comput. Sci., 14:2 (2012), 37–56  mathscinet  zmath  isi  elib
    20. Le N.C., Brause Ch., Schiermeyer I., “New Sufficient Conditions For Alpha-Redundant Vertices”, Discrete Math., 338:10, SI (2015), 1674–1680  crossref  mathscinet  zmath  isi  elib  scopus
    21. Le N.C., Brause Ch., Schiermeyer I., “Extending the Max Algorithm For Maximum Independent Set”, Discuss. Math. Graph Theory, 35:2 (2015), 365–386  crossref  mathscinet  zmath  isi  elib  scopus
    22. В. Е. Алексеев, Д. В. Захарова, “Независимые множества в графах без поддеревьев с большим числом листьев”, Дискретн. анализ и исслед. опер., 23:1 (2016), 5–16  mathnet  crossref  mathscinet  elib; V. E. Alekseev, D. V. Zakharova, “Independent sets in graphs without subtrees with many leaves”, J. Appl. Industr. Math., 10:1 (2016), 1–6  crossref
    23. Brandstaedt A., Mosca R., “Maximum Weight Independent Set For Lclaw-Free Graphs in Polynomial Time”, Discrete Appl. Math., 237 (2018), 57–64  crossref  mathscinet  zmath  isi  scopus
    24. Brandstaedt A., Mosca R., “Maximum Weight Independent Sets For (P-7,Triangle)-Free Graphs in Polynomial Time”, Discrete Appl. Math., 236 (2018), 57–65  crossref  mathscinet  zmath  isi  scopus
    25. В. Е. Алексеев, С. В. Сорочан, “Новые случаи полиномиальной разрешимости задачи о независимом множестве для графов с запрещёнными путями”, Дискретн. анализ и исслед. опер., 25:2 (2018), 5–18  mathnet  crossref  elib; V. E. Alekseev, S. V. Sorochan, “New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths”, J. Appl. Industr. Math., 12:2 (2018), 213–219  crossref
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:581
    Полный текст:221
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021