Bi-induced sub graphs and stability number
DOI:
https://doi.org/10.2298/YJOR0401027ZKeywords:
stability number, hereditary class, bi-hereditary class, forbidden induced sub graphs, forbidden bi-induced sub graphsAbstract
We define a 2-parametric hierarchy CLAP (m, n) of bi-hereditary classes of graphs, and show that a maximum stable set can be found in polynomial time within each class CLAP (m, n). The classes can be recognized in polynomial time.References
Alekseev, V.E., "On easy and hard hereditary classes of graphs for the independent set problem", Discrete Appl. Math. (to appear)
Branstiidt, A., and Hammer, P.L., "On the stability number of claw-free P5-free and more general graphs", Discrete Appl. Math., 95 (1-3) (1999) 163-167.
Garey, M.R., and Johnson, D.S., Computers and intractability. A guide to the theory of NP completeness, W. H. Freeman and Co., San Francisco, Calif., 1979.
Hall, M. Jr., Combinatorial theory, Blaisdell Publ. Co., Waltham, 1967.
Hall, P., "On representatives of subsets", J. London Math. Soc, 10 (1935) 26-30.
Hertz, A., "Polynomially solvable cases for the maximum stable set problem", Discrete Appl. Math, 60 (1-3) (1995) 195-210.
Karp, R.M., "Reducibility among combinatorial problems", in: Complexity of computer computations, Plenum Press, New York, 1972, 85-103.
Lozin, V., and Rautenbach, D., "Some results on graphs without long induced paths", RUTCOR Research Report RRR 6-2003, RUTCOR, Rutgers University, 2003.
Mahadev, N.V.R., "Vertex deletion and stability number", Technical Report ORWP 90/2, Swiss Federal Institute of Technology, 1990.
Mosca, R., "Polynomial algorithms for the maximum stable set problem on particular classes of P5-free graphs", Inform. Process. Lett, 61 (3) (1997) 137-144.
Downloads
Published
Issue
Section
License
Copyright (c) 2004 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
