The Library
Boundary properties of graphs for algorithmic graph problems
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. 35453554. ISSN 03043975
Full text not available from this repository.
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 kCOLORABILITY. 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 kCOLORABILITY.
Item Type:  Journal Article  

Subjects:  Q Science > QA Mathematics  
Divisions:  Faculty of Science > Computer Science Faculty of 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:  03043975  
Official Date:  1 July 2011  
Dates: 


Volume:  Vol.412  
Number:  No.29  
Page Range:  pp. 35453554  
Identification Number:  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:  100100357a (RFFI), 61.1 (GU VShĖ), 20101.3.1111017012 (FAP)  
References:  [1] V.E. Alekseev, Range of values of entropy of hereditary classes of graphs, Diskret. Math. 4 (2) (1992) 148–157 (in Russian); translation in Discrete 

URI:  http://wrap.warwick.ac.uk/id/eprint/38771 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Actions (login required)
View Item 