Stable sets for ( P ₆ , K 2 , 3 ) -free graphs

Raffaele Mosca

Discussiones Mathematicae Graph Theory (2012)

  • Volume: 32, Issue: 3, page 387-401
  • ISSN: 2083-5892

Abstract

top
The Maximum Stable Set (MS) problem is a well known NP-hard problem. However different graph classes for which MS can be efficiently solved have been detected and the augmenting graph technique seems to be a fruitful tool to this aim. In this paper we apply a recent characterization of minimal augmenting graphs [22] to prove that MS can be solved for ( P ₆ , K 2 , 3 ) -free graphs in polynomial time, extending some known results.

How to cite

top

Raffaele Mosca. "Stable sets for $(P₆,K_{2,3})$-free graphs." Discussiones Mathematicae Graph Theory 32.3 (2012): 387-401. <http://eudml.org/doc/270954>.

@article{RaffaeleMosca2012,
abstract = {The Maximum Stable Set (MS) problem is a well known NP-hard problem. However different graph classes for which MS can be efficiently solved have been detected and the augmenting graph technique seems to be a fruitful tool to this aim. In this paper we apply a recent characterization of minimal augmenting graphs [22] to prove that MS can be solved for $(P₆,K_\{2,3\})$-free graphs in polynomial time, extending some known results.},
author = {Raffaele Mosca},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph algorithms; stable sets; P₆-free graphs; -free graphs},
language = {eng},
number = {3},
pages = {387-401},
title = {Stable sets for $(P₆,K_\{2,3\})$-free graphs},
url = {http://eudml.org/doc/270954},
volume = {32},
year = {2012},
}

TY - JOUR
AU - Raffaele Mosca
TI - Stable sets for $(P₆,K_{2,3})$-free graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 3
SP - 387
EP - 401
AB - The Maximum Stable Set (MS) problem is a well known NP-hard problem. However different graph classes for which MS can be efficiently solved have been detected and the augmenting graph technique seems to be a fruitful tool to this aim. In this paper we apply a recent characterization of minimal augmenting graphs [22] to prove that MS can be solved for $(P₆,K_{2,3})$-free graphs in polynomial time, extending some known results.
LA - eng
KW - graph algorithms; stable sets; P₆-free graphs; -free graphs
UR - http://eudml.org/doc/270954
ER -

References

top
  1. [1] V.E. Alekseev, On the local restriction effect on the complexity of finding the graph independence number in: Combinatorial-algebraic Methods in Applied Mathematics, (Gorkiy University Press, Gorkiy, 1983) 3-13 (in Russian). 
  2. [2] V.E. Alekseev, A polynomial algorithm for finding largest independent sets in fork-free graphs, Discrete Anal. Oper. Res., Ser. 1, 6 (1999) 3-19 (in Russian) (see also [3] for the English version). 
  3. [3] V.E. Alekseev, A polynomial algorithm for finding largest independent sets in fork-free graphs, Discrete Applied Math. 135 (2004) 3-16, doi: 10.1016/S0166-218X(02)00290-1. 
  4. [4] V.E. Alekseev, On easy and hard hereditary classes of graphs with respect to the independent set problem, Discrete Applied Math. 132 (2004) 17-26, doi: 10.1016/S0166-218X(03)00387-1. 
  5. [5] V.E. Alekseev and V.V. Lozin, Augmenting graphs for independent sets, Discrete Applied Math. 145 (2004) 3-10, doi: 10.1016/j.dam.2003.09.003. Zbl1056.05131
  6. [6] G. Bacsó and Zs. Tuza, A characterization of graphs without long induced paths, J. Graph Theory 14 (1990) 455-464, doi: 10.1002/jgt.3190140409. 
  7. [7] A. Brandstädt and Chính T. Hoáng, On clique separators, nearly chordal graphs and the Maximum Weight Stable Set problem, Theoretical Computer Science 389 (2007)) 295-306, doi: 10.1016/j.tcs.2007.09.031. Zbl1143.68059
  8. [8] A. Brandstädt, V.B. Le and J.P. Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Math. Appl. (vol. 3, SIAM, Philadelphia, 1999). Zbl0919.05001
  9. [9] A. Brandstädt, T. Klembt and S. Mahfud, P₆- and Triangle-Free Graphs Revisited: Structure and Bounded Clique-Width, Discrete Math. and Theoretical Computer Science 8 (2006) 173-188. Zbl1153.05040
  10. [10] J. Dong, On the i-diameter of i-center in a graph without long induced paths, J. Graph Theory 30 (1999) 235-241, doi: 10.1002/(SICI)1097-0118(199903)30:3<235::AID-JGT8>3.0.CO;2-C. Zbl0922.05024
  11. [11] M. Farber, On diameters and radii of bridged graphs, Discrete Math. 73 (1989) 249-260, doi: 10.1016/0012-365X(89)90268-9. Zbl0667.05036
  12. [12] J.-L. Fouquet, V. Giakoumakis and J.-M. Vanherpe, Bipartite graphs totally decomposable by canonical decomposition, International J. Foundations of Computer Science 10 (1999) 513-533, doi: 10.1142/S0129054199000368. Zbl1320.05093
  13. [13] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completness (Freeman, San Francisco, CA, 1979). Zbl0411.68039
  14. [14] M.U. Gerber, A. Hertz and V.V. Lozin, Stable sets in two subclasses of banner-free graphs, Discrete Applied Math. 132 (2004) 121-136, doi: 10.1016/S0166-218X(03)00395-0. Zbl1029.05145
  15. [15] M.U. Gerber and V.V. Lozin, On the stable set problem in special P₅-free graphs, Discrete Applied Math. 125 (2003) 215-224, doi: 10.1016/S0166-218X(01)00321-3. Zbl1028.05103
  16. [16] V. Giakoumakis and J.-M. Vanherpe, Linear time recognition and optimization for weak-bisplit graphs, bi-cographs and bipartite P₆-free graphs, International J. Foundations of Computer Science 14 (2003) 107-136, doi: 10.1142/S0129054103001625. Zbl1099.68680
  17. [17] A. Hertz and V.V. Lozin The maximum independent set problem and augmenting graphs, Graph Theory and Combinatorial Optimization, GERAD 25th Anniv., Springer, New York (2005) 69-99. 
  18. [18] P. van't Hof and D. Paulusma, A new characterization of P₆-free graphs, Discrete Applied Math. 158 (2010) 731-740, doi: 10.1016/j.dam.2008.08.025. Zbl1225.05145
  19. [19] J. Liu, Y. Peng and C. Zhao, Characterization of P₆-free graphs, Discrete Applied Math. 155 (2007) 1038-1043, doi: 10.1016/j.dam.2006.11.005. Zbl1117.05082
  20. [20] J. Liu and H. Zhou, Dominating subgraphs in graphs with some forbidden structure, Discrete Math. 135 (1994) 163-168, doi: 10.1016/0012-365X(93)E0111-G. Zbl0812.05052
  21. [21] V.V. Lozin and M. Milanič, A polynomial algorithm to find an independent set of maximum weight in a fork-free graph, J. Discrete Algorithms 6 (2008) 595-604, doi: 10.1016/j.jda.2008.04.001. Zbl1154.90607
  22. [22] V.V. Lozin and M. Milanič, On finding augmenting graphs, Discrete Applied Math. 156 (2008) 2517-2529, doi: 10.1016/j.dam.2008.03.008. Zbl1159.05313
  23. [23] V.V. Lozin and R. Mosca, Independent sets in extensions of 2K₂-free graphs, Discrete Applied Math. 146 (2005) 74-80, doi: 10.1016/j.dam.2004.07.006. Zbl1087.90080
  24. [24] V.V. Lozin and D. Rautenbach, Some results on graphs without long induced paths, Information Processing Letters 88 (2003) 167-171, doi: 10.1016/j.ipl.2003.07.004. Zbl1178.68285
  25. [25] 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. Zbl0434.05043
  26. [26] R. Mosca, Stable sets in certain P₆-free graphs, Discrete Applied Math. 92 (1999) 177-191, doi: 10.1016/S0166-218X(99)00046-3. Zbl0929.05076
  27. [27] R. Mosca, Some observations on maximum weight stable sets in certain P₅-free graphs, European J. Operational Research 184 (2008) 849-859, doi: 10.1016/j.ejor.2006.12.011. Zbl1141.05068
  28. [28] R. Mosca, Independent sets in (P₆,diamond)-free graphs, Discrete Math. and Theoretical Computer Science 11:1 (2009) 125-140. Zbl1196.05065
  29. [29] O.J. Murphy, Computing independent sets in graphs with large girth, Discrete Applied Math. 35 (1992) 167-170, doi: 10.1016/0166-218X(92)90041-8. Zbl0769.05053
  30. [30] N. Sbihi, Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile, Discrete Math. 29 (1980) 53-76, doi: 10.1016/0012-365X(90)90287-R. Zbl0444.05049

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.