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., 2018, Volume 25, Issue 2, Pages 5–18 (Mi da893)  

New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths

V. E. Alekseev, S. V. Sorochan

Lobachevskii Nizhniy Novgorod State University, IITMM, 23 Gagarin Ave., 603950 Nizhny Novgorod, Russia

Abstract: The independent set problem is solvable in polynomial time for the graphs not containing the path $P_k$ for any fixed $k$. If the induced path $P_k$ is forbidden then the complexity of this problem is unknown for $k>6$. We consider the intermediate cases that the induced path $P_k$ and some of its spanning supergraphs are forbidden. We prove the solvability of the independent set problem in polynomial time for the following cases: (1) the supergraphs whose minimal degree is less than $k/2$ are forbidden; (2) the supergraphs whose complementary graph has more than $k/2$ edges are forbidden; (3) the supergraphs from which we can obtain $P_k$ by means of graph intersection are forbidden. Bibliogr. 12.

Keywords: independent set, forbidden subgraph, path, supergraph, polynomial time.

Funding Agency Grant Number
Russian Foundation for Basic Research 17-01-00710a


DOI: https://doi.org/10.17377/daio.2018.25.581

Full text: PDF file (328 kB)
References: PDF file   HTML file

English version:
Journal of Applied and Industrial Mathematics, 2018, 12:2, 213–219

UDC: 519.178
Received: 08.06.2017
Revised: 22.11.2017

Citation: V. E. Alekseev, S. V. Sorochan, “New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths”, Diskretn. Anal. Issled. Oper., 25:2 (2018), 5–18; J. Appl. Industr. Math., 12:2 (2018), 213–219

Citation in format AMSBIB
\Bibitem{AleSor18}
\by V.~E.~Alekseev, S.~V.~Sorochan
\paper New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths
\jour Diskretn. Anal. Issled. Oper.
\yr 2018
\vol 25
\issue 2
\pages 5--18
\mathnet{http://mi.mathnet.ru/da893}
\crossref{https://doi.org/10.17377/daio.2018.25.581}
\elib{https://elibrary.ru/item.asp?id=32729776}
\transl
\jour J. Appl. Industr. Math.
\yr 2018
\vol 12
\issue 2
\pages 213--219
\crossref{https://doi.org/10.1134/S1990478918020023}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85047800693}


Linking options:
  • http://mi.mathnet.ru/eng/da893
  • http://mi.mathnet.ru/eng/da/v25/i2/p5

    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
  • Дискретный анализ и исследование операций
    Number of views:
    This page:142
    Full text:19
    References:19
    First page:2

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