RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskretn. Anal. Issled. Oper., Ser. 1, 1999, Volume 6, Issue 4, Pages 3–19 (Mi da324)  

This article is cited in 25 scientific papers (total in 25 papers)

A polynomial algorithm for finding the largest independent sets in claw-free graphs

V. E. Alekseev

N. I. Lobachevski State University of Nizhni Novgorod

Full text: PDF file (2217 kB)

Bibliographic databases:
UDC: 519.17
Received: 14.01.1999
Revised: 19.07.1999

Citation: V. E. Alekseev, “A polynomial algorithm for finding the largest independent sets in claw-free graphs”, Diskretn. Anal. Issled. Oper., Ser. 1, 6:4 (1999), 3–19

Citation in format AMSBIB
\Bibitem{Ale99}
\by V.~E.~Alekseev
\paper A~polynomial algorithm for finding the largest independent sets in claw-free graphs
\jour Diskretn. Anal. Issled. Oper., Ser.~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}


Linking options:
  • http://mi.mathnet.ru/eng/da324
  • http://mi.mathnet.ru/eng/da/v6/s1/i4/p3

    SHARE: 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

    This publication is cited in the following articles:
    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. V. E. Alekseev, D. V. Zakharova, “Independent sets in graphs without subtrees with many leaves”, J. Appl. Industr. Math., 10:1 (2016), 1–6  mathnet  crossref  crossref  mathscinet  elib
    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. 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  mathnet  crossref  crossref  elib
  • Дискретный анализ и исследование операций
    Number of views:
    This page:585
    Full text:221

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2021