Boundary classes of graphs for the dominating set problem
- Alekseev, Vladimir E
- Korobitsyn, Dmitry V
- Lozin, Vadim V
Publication date
August 2004
DOI Publisher
Elsevier B.V. ISSN
0012-365X Citation count (estimate)
29Abstract
AbstractThe notion of a boundary class has been recently introduced as a tool for classification of hereditary classes of graphs according to the time complexity of NP-hard graph problems. In the present paper we concentrate on the dominating set problem and obtain three boundary classes for it
Add to ORKG