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. (to appear) On easy and hard hereditary classes of graphs for the independent set problem. Discrete Applied Mathematics
Branstiidt, A., Hammer, P.L. (1999) On the stability number of claw-free P5-free and more general graphs. Discrete Applied Mathematics, 95, (1-3), 163-167
Garey, M.R., Johnson, D.S. (1978) Computers and intractability: A guide to the theory of NP-completeness. San Francisco, CA, itd: W.H. Freeman Publishing
Hall, M.Jr. (1967) Combinatorial theory. Waltham, MA: Blaisdell Publishing
Hall, P. (1935) On representatives of subsets. Journal of the London Mathematical Society, 10, 26-30
Hertz, A. (1995) Polynomially solvable cases for the maximum stable set problem. Discrete Applied Mathematics, 60, 3, 195-210
Karp, R.M. (1972) Reducibility among combinatorial problems. u: Miller R.E.,Thatcher J.W. [ur.] Complexity of computer computations, New York-London: Plenum Press, str. 85-103
Lozin, V., Rautenbach, D. (2003) Some results on graphs without long induced paths. RUTCOR Research Report RRR 6-2003, RUTCOR, Rutgers University
Mahadev, N.V.R. (1990) Vertex deletion and stability number. Zurich: Swiss Federal Institute of Technology, Technical Report ORWP 90/2
Mosca, R. (1997) Polynomial algorithms for the maximum stable set problem on particular classes of $Psb 5$-free graphs. Information Processing Letters, 61, 3, 137-143
Downloads
Published
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
