PL EN

Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo

## Discussiones Mathematicae Graph Theory

2015 | 35 | 2 | 365-386
Tytuł artykułu

### Extending the MAX Algorithm for Maximum Independent Set

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
The maximum independent set problem is an NP-hard problem. In this paper, we consider Algorithm MAX, which is a polynomial time algorithm for finding a maximal independent set in a graph G. We present a set of forbidden induced subgraphs such that Algorithm MAX always results in finding a maximum independent set of G. We also describe two modifications of Algorithm MAX and sets of forbidden induced subgraphs for the new algorithms.
Słowa kluczowe
EN
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
365-386
Opis fizyczny
Daty
wydano
2015-05-01
otrzymano
2014-01-31
poprawiono
2015-01-07
zaakceptowano
2015-01-07
online
2015-04-18
Twórcy
autor
• School of Applied Mathematics and Informatics Hanoi University of Science and Technology, lechingoc@yahoo.com
• Faculty of Mathematics and Computer Science Technische Universität Bergakademie Freiberg
autor
autor
Bibliografia
• [1] V.E. Alekseev, On the ocal restrictions effect on the complexity of finding the graph independence number , in: Combinatorial-Algebraic Methods in Applied Mathematics, A. Markov (Ed(s)), (Gorkiy University, 1983) 3-13, in Russian.
• [2] V.E. Alekseev, A polynomial algorithm for finding maximum independent sets in fork-free graphs, Discrete Anal. Operation Research Serie 1 6(4) (1999) 3-19, in Russian.
• [3] V.E. Alekseev, Augmenting graphs for independent sets, Discrete Appl. Math. 145 (2004) 3-10. doi:10.1016/j.dam.2003.09.003[Crossref]
• [4] A. Billionnet, Reductions and optimality conditions in the problem of a maximum weighted stable set , RAIRO Recherche Opérationnelle 15(3) (1999) 213-231, in French.
• [5] A. Brandstädt and V.V. Lozin, A note on -redundant vertices in graphs, Discrete Appl. Math. 108 (2001) 301-308. doi:10.1016/S0166-218X(00)00239-0[Crossref]
• [6] A. Brandstädt, H.O. Le, V.B. Le, On -redundant vertices in P5-free graphs, Inform. Process. Lett. 82 (2002) 119-122. doi:10.1016/S0020-0190(01)00265-4[Crossref]
• [7] L. Butz, P.L. Hammer and D. Haussmann, Reduction methods for the vertex packing problem, in: Proceedings of the 17th Conference on Probability Theory, Brasov, Romania, 1982, M. Iosifescu, T. Postelnicu, S. Grigorescu (Ed(s)), (Utrecht, VNU Science Press, 1985) 73-79.
• [8] J. Chen, I.A. Kanji and W. Jia, Vertex cover: further observations and further improvement , J. Algorithms 41 (2001) 280-301. doi:10.1006/jagm.2001.1186[Crossref]
• [9] D.G. Corneil, H. Lerchs and L.S. Burlingham, Complement reducible graphs, Discrete Appl. Math. 3 (1981) 163-174. doi:10.1016/0166-218X(81)90013-5[Crossref]
• [10] D.G. Corneil, Y. Perl and L.K. Stewart, A linear recognition algorithm for cographs, SIAM J. Comput. 14 (1985) 926-934. doi:10.1137/0214065[Crossref]
• [11] C. Ebenegger, P.L. Hammer and D. Werra, Pseudo-Boolean functions and stability of graphs, Ann. Discrete Math. 19 (1984) 83-98.
• [12] M.U. Gerber and V.V. Lozin, Robust algorithms for the stable set problem, Graphs Combin. 19 (2003) 347-356. doi:10.1007/s00373-002-0517-5[Crossref]
• [13] M.U. Gerber and V.V. Lozin, On the stable set problem in special P5-free graphs, Discrete Appl. Math. 125 (2003) 215-224. doi:10.1016/S0166-218X(01)00321-3[Crossref]
• [14] M.C. Golumbic and P.L. Hammer, Stability in circular arc graphs, J. Algorithms 9 (1988) 314-320. doi:10.1016/0196-6774(88)90023-5[Crossref]
• [15] J.R. Griggs, Lower bounds on the independence number in terms of the degree, J. Combin. Theory (B) 34 (1983) 22-39. doi:10.1016/0095-8956(83)90003-5[Crossref]
• [16] P.L. Hammer and A. Hertz, On a transformation which preserves the stability number( RUTCOR Research report, Rutgers University1991) 69-91.
• [17] J. Harant, Z. Ryjáček and I. Schiermeyer, Forbidden subgraphs implying the MINalgorithm gives a maximum independent set , Discrete Math. 256 (2002) 193-201. doi:10.1016/S0012-365X(02)00571-X[Crossref]
• [18] A. Hertz, On the use Boolean methods for the computation of the stability number , Discrete Appl. Math. 76 (1997) 183-203. doi:10.1016/S0166-218X(96)00124-2[Crossref]
• [19] A. Hertz and V.V. Lozin, The maximum independent set problem and augmenting graphs, in: Graph Theory Combin. Optim., D. Avis, A. Hertz, O. Marcotte (Ed(s)), (Springer, 2005) 69-99.
• [20] N.C. Lê, C. Brause and I. Schiermeyer, New sufficient conditions for -redundant vertices, Discrete Math. (2014) in press. doi:10.1016/j.disc.2014.07.002[Crossref]
• [21] D. Lokshtanov, M. Vatshelle and Y. Villanger, Independent set in P5-free graphs in polynomial time, Technical Report (2013). www.ii.uib.no/~martinv/Papers/ISinP5free.pdf
• [22] V.V. Lozin and D. Rautenbach, Some results on graphs without long induced paths, Inform. Process. Lett. 88 (2004) 167-171. doi:10.1016/j.ipl.2003.07.004 [Crossref]
• [23] V.V. Lozin and M. Milanič, Maximum independent sets in graphs of low degree, in: Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms SoDA’ 07, H. Gabow (Ed(s)), (Society for Industrial and Applied Mathematics, 2007) 874-880.
• [24] V.V. Lozin and M. Milanič, On finding augmenting graphs, Discrete Appl. Math. 156 (2008) 2517-2529. doi:10.1016/j.dam.2008.03.008[Crossref]
• [25] V.V. Lozin and R.Mosca, Maximum independent sets in subclasses of P5-free graphs, Inform. Process. Lett. 109 (2009) 319-324. doi:10.1016/j.ipl.2008.11.005[Crossref]
• [26] V.V. Lozin, J. Monnot and B. Ries, On the maximum independent set problem in subclasses of subcubic graphs, in: International Workshop on Combinatorial Algorithms IWOCA 2013, T. Lecroq, L. Mouchard (Ed(s)), (Springer, 2013) 314-326.
• [27] N.V.R. Mahadev and B.A. Reed, A note on vertex orders for stability number , J. Graph Theory 30 (1999) 113-120. doi:10.1002/(SICI)1097-0118(199902)30:2h113::AID-JGT5i3.0.CO;2-#[Crossref]
• [28] G.J. Minty, On maximal independent sets of vertices in claw-free graphs, J. Combin. Theory (B) 28 (1980) 284-304. doi:10.1016/0095-8956(80)90074-X[Crossref]
• [29] R. Mosca, Independent sets in (P6,diamond)-free graphs, Discrete Math. Theor. Comput. Sci. 11 (2009) 125-140.
• [30] R. Mosca, Stable sets for (P6,K2 , 3)-free graphs, Discuss. Math. Graph Theory 32 (2012) 387-401. doi:10.7151/dmgt.1598[Crossref][WoS]
• [31] O.J. Murphy, Lower bounds on the stability number of graphs computed in terms of degrees, Discrete Math. 90 (1991) 207-211. doi:10.1016/0012-365X(91)90357-8[Crossref]
• [32] O.J. Murphy, Computing independent sets in graphs with large girth, Discrete Appl. Math. 35 (1992) 167-170. doi:0.1016/0166-218X(92)90041-8
• [33] D.J. Rose, R.E. Tarjan and G.S. Lueker, Algorithmic aspects of vertex elimination of graphs, SIAM J. Comput. 5 (1976) 266-283. doi:10.1137/0205021[Crossref]
• [34] N. Sbihi, Algorithme de recherche d’un stable de cardinalité maximum dans un graphe sans étoile, Discrete Math. 29 (1980) 53-76.
• [35] I.E. Zverovich, Minimum degree algorithms for stability number , Discrete Appl. Math. 132 (2004) 211-216. doi:10.1016/0012-365X(90)90287-R[Crossref]
• [36] I.E. Zverovich and O.I. Zverovich, Stability number in subclasses of P5-free graphs, Appl. Math. J. Chinese Univ. Ser. B 19 (2004) 125-132. doi:10.1007/s11766-004-0045-6 [Crossref]
Typ dokumentu
Bibliografia
Identyfikatory