|
|
Дискретн. анализ и исслед. опер., сер. 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
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
Lozin V.V., “Bipartite graphs without a skew star”, Discrete Math, 257:1 (2002), 83–100
   -
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
-
Alexe G., Hammer P.L., Lozin V.V., de Werra D., “Struction revisited”, Discrete Appl Math, 132:1–3 (2003), 27–46
-
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
-
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
-
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
-
Mosca R., “Some results on maximum stable sets in certain P-5-free graphs”, Discrete Appl Math, 132:1–3 (2003), 175–183
-
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
-
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
-
Hertz A., Lozin V., Schindl D., “Finding augmenting chains in extensions of claw-free graphs”, Inform Process Lett, 86:6 (2003), 311–316
-
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
-
Alekseev V.E., Lozin V.V., “Augmenting graphs for independent sets”, Discrete Appl Math, 145:1 (2004), 3–10
-
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
-
Zverovich I.E., Zverovich I.I., “Penta-extensions of hereditary classes of graphs”, J Comb Optim, 10:2 (2005), 169–178
-
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
-
Hougardy S., “Classes of perfect graphs”, Discrete Math, 306:19–20 (2006), 2529–2571
 -
Mosca R., “Stable sets of maximum weight in (P-7, banner)-free graphs”, Discrete Math, 308:1 (2008), 20–33
-
Mosca R., “Some observations on maximum weight stable sets in certain P-5-free graphs”, European J Oper Res, 184:3 (2008), 849–859
-
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
-
Le N.C., Brause Ch., Schiermeyer I., “New Sufficient Conditions For Alpha-Redundant Vertices”, Discrete Math., 338:10, SI (2015), 1674–1680
-
Le N.C., Brause Ch., Schiermeyer I., “Extending the Max Algorithm For Maximum Independent Set”, Discuss. Math. Graph Theory, 35:2 (2015), 365–386
-
В. Е. Алексеев, Д. В. Захарова, “Независимые множества в графах без поддеревьев с большим числом листьев”, Дискретн. анализ и исслед. опер., 23:1 (2016), 5–16
 ; V. E. Alekseev, D. V. Zakharova, “Independent sets in graphs without subtrees with many leaves”, J. Appl. Industr. Math., 10:1 (2016), 1–6 -
Brandstaedt A., Mosca R., “Maximum Weight Independent Set For Lclaw-Free Graphs in Polynomial Time”, Discrete Appl. Math., 237 (2018), 57–64
-
Brandstaedt A., Mosca R., “Maximum Weight Independent Sets For (P-7,Triangle)-Free Graphs in Polynomial Time”, Discrete Appl. Math., 236 (2018), 57–65
-
В. Е. Алексеев, С. В. Сорочан, “Новые случаи полиномиальной разрешимости задачи о независимом множестве для графов с запрещёнными путями”, Дискретн. анализ и исслед. опер., 25:2 (2018), 5–18 ; 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
|
| Просмотров: |
| Эта страница: | 581 | | Полный текст: | 221 |
|
Пользовательское соглашение