The Library
Boundary properties of graphs for algorithmic graph problems
Tools
Tools
Tools
Korpelainen, Nicholas, Lozin, Vadim V., Malyshev, Dmitriy S. and Tiskin, Alexander (2011) Boundary properties of graphs for algorithmic graph problems. Theoretical Computer Science, Vol.412 (No.29). pp. 3545-3554. doi:10.1016/j.tcs.2011.03.001 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.2011.03.001
Abstract
The notion of a boundary graph property was recently introduced as a relaxation of that of a minimal property and was applied to several problems of both algorithmic and combinatorial nature. In the present paper, we first survey recent results related to this notion and then apply it to two algorithmic graph problems: HAMILTONIAN CYCLE and VERTEX k-COLORABILITY. In particular, we discover the first two boundary classes for the HAMILTONIAN CYCLE problem and prove that for any k > 3 there is a continuum of boundary classes for VERTEX k-COLORABILITY.
| Item Type: | Journal Article | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics |
||||
| Library of Congress Subject Headings (LCSH): | Computational complexity, Hamiltonian graph theory, Graph theory, Graph coloring | ||||
| Journal or Publication Title: | Theoretical Computer Science | ||||
| Publisher: | Elsevier Science BV | ||||
| ISSN: | 0304-3975 | ||||
| Official Date: | 1 July 2011 | ||||
| Dates: |
|
||||
| Volume: | Vol.412 | ||||
| Number: | No.29 | ||||
| Page Range: | pp. 3545-3554 | ||||
| DOI: | 10.1016/j.tcs.2011.03.001 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Funder: | University of Warwick. Centre for Discrete Mathematics and Its Applications (DIMAP), Rossiĭskiĭ fond fundamentalʹnykh issledovaniĭ [Russian Foundation for Basic Research] (RFFI), Gosudarstvennyĭ universitet Vysshai︠a︡ shkola ėkonomiki (Russia) (GU VShĖ), FAP | ||||
| Grant number: | 10-01-00357-a (RFFI), 61.1 (GU VShĖ), 2010-1.3.1-111-017-012 (FAP) |
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 |
