The Library
A decidability result for the dominating set problem
Tools
Tools
Tools
Lozin, Vadim V.. (2010) A decidability result for the dominating set problem. Theoretical Computer Science, Vol.411 (No.44-46). pp. 4023-4027. ISSN 0304-3975
Full text not available from this repository.
Official URL: http://dx.doi.org/10.1016/j.tcs.2010.08.027
Abstract
We study the following question: given a finite collection of graphs G(1), ..., G(k), is the dominating set problem polynomial-time solvable in the class of (G(1), ..., G(k))-free graphs? In this paper, we prove the existence of an efficient algorithm that answers this question for k = 2. (C) 2010 Elsevier B.V. All rights reserved.
| Item Type: | Journal Article |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
| Divisions: | Faculty of Science > Mathematics |
| Journal or Publication Title: | Theoretical Computer Science |
| Publisher: | Elsevier Science BV |
| ISSN: | 0304-3975 |
| Date: | 25 October 2010 |
| Volume: | Vol.411 |
| Number: | No.44-46 |
| Number of Pages: | 5 |
| Page Range: | pp. 4023-4027 |
| Identification Number: | 10.1016/j.tcs.2010.08.027 |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| Access rights to Published version: | Restricted or Subscription Access |
| Funder: | DIMAP (the Centre for Discrete Mathematics and its Applications at the University of Warwick) |
| URI: | http://wrap.warwick.ac.uk/id/eprint/4901 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
