Standard

Boundary properties of graphs for algorithmic graph problems. / Korpelainen, Nicholas; Lozin, Vadim V.; Malyshev, Dmitriy S.; Tiskin, Alexander.

в: Theoretical Computer Science, Том 412, № 29, 01.07.2011, стр. 3545-3554.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

Harvard

Korpelainen, N, Lozin, VV, Malyshev, DS & Tiskin, A 2011, 'Boundary properties of graphs for algorithmic graph problems', Theoretical Computer Science, Том. 412, № 29, стр. 3545-3554. https://doi.org/10.1016/j.tcs.2011.03.001

APA

Korpelainen, N., Lozin, V. V., Malyshev, D. S., & Tiskin, A. (2011). Boundary properties of graphs for algorithmic graph problems. Theoretical Computer Science, 412(29), 3545-3554. https://doi.org/10.1016/j.tcs.2011.03.001

Vancouver

Korpelainen N, Lozin VV, Malyshev DS, Tiskin A. Boundary properties of graphs for algorithmic graph problems. Theoretical Computer Science. 2011 Июль 1;412(29):3545-3554. https://doi.org/10.1016/j.tcs.2011.03.001

Author

Korpelainen, Nicholas ; Lozin, Vadim V. ; Malyshev, Dmitriy S. ; Tiskin, Alexander. / Boundary properties of graphs for algorithmic graph problems. в: Theoretical Computer Science. 2011 ; Том 412, № 29. стр. 3545-3554.

BibTeX

@article{2b55d6428c95443eaf15e6031403965a,
title = "Boundary properties of graphs for algorithmic graph problems",
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. {\textcopyright} 2011 Elsevier B.V. All rights reserved.",
keywords = "Computational complexity, Hamiltonian cycle, Hereditary class, Vertex colorability",
author = "Nicholas Korpelainen and Lozin, {Vadim V.} and Malyshev, {Dmitriy S.} and Alexander Tiskin",
year = "2011",
month = jul,
day = "1",
doi = "10.1016/j.tcs.2011.03.001",
language = "English",
volume = "412",
pages = "3545--3554",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "29",

}

RIS

TY - JOUR

T1 - Boundary properties of graphs for algorithmic graph problems

AU - Korpelainen, Nicholas

AU - Lozin, Vadim V.

AU - Malyshev, Dmitriy S.

AU - Tiskin, Alexander

PY - 2011/7/1

Y1 - 2011/7/1

N2 - 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. © 2011 Elsevier B.V. All rights reserved.

AB - 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. © 2011 Elsevier B.V. All rights reserved.

KW - Computational complexity

KW - Hamiltonian cycle

KW - Hereditary class

KW - Vertex colorability

UR - http://www.scopus.com/inward/record.url?scp=79956356522&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2011.03.001

DO - 10.1016/j.tcs.2011.03.001

M3 - Article

AN - SCOPUS:79956356522

VL - 412

SP - 3545

EP - 3554

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 29

ER -

ID: 127708854