Boundary properties of graphs for algorithmic graph problems期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

Boundary properties of graphs for algorithmic graph problems

Authors:	Nicholas Korpelainen Dmitriy S Malyshev Alexander Tiskin

Affiliation:	^a DIMAP and Mathematics Institute, University of Warwick, Coventry, CV4 7AL, UK ^b Department of Applied Mathematics and Informatics, Higher School of Economics (Nizhny Novgorod branch), Bolshaya Pecherskaya str. 25/12, 603155, Nizhny Novgorod, Russia ^c Department of Mathematical Logic and Higher Algebra, University of Nizhny Novgorod, Gagarina av. 23, 603950, Nizhny Novgorod, Russia ^d DIMAP and Department of Computer Science, University of Warwick, Coventry, CV4 7AL, UK

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 vertexk-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 vertexk-colorability.

Keywords:	Computational complexity Hereditary class Hamiltonian cycle Vertex colorability
本文献已被 ScienceDirect 等数据库收录！