2002-38: Boundary classes of graphs for the dominating set problem

DIMACS TR: 2002-38

Boundary classes of graphs for the dominating set problem

Authors: V.E. Alekseev, D.V. Korobitsyn and V.V. Lozin

ABSTRACT
The 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.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-38.ps.gz

DIMACS Home Page