The Library
NP-hard graph problems and boundary classes of graphs
Tools
Alekseev, V. E., Boliac, R., Korobitsyn, D. V. and Lozin, Vadim V. (2007) NP-hard graph problems and boundary classes of graphs. Theoretical Computer Science, Vol.389 (No.1-2). pp. 219-236. doi:10.1016/j.tcs.2007.09.013 ISSN 0304-3975.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.tcs.2007.09.013
Abstract
Any graph problem, which is NP-hard in general graphs, becomes polynomial-time solvable when restricted to graphs in special classes. When does a difficult problem become easy? To answer this question we study the notion of boundary classes. In the present paper we define this notion in its most general form, describe several approaches to identify boundary classes and apply them to various graph problems.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Theoretical Computer Science | ||||
Publisher: | Elsevier Science BV | ||||
ISSN: | 0304-3975 | ||||
Official Date: | 10 December 2007 | ||||
Dates: |
|
||||
Volume: | Vol.389 | ||||
Number: | No.1-2 | ||||
Number of Pages: | 18 | ||||
Page Range: | pp. 219-236 | ||||
DOI: | 10.1016/j.tcs.2007.09.013 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |