Logo BSU

Please use this identifier to cite or link to this item: https://elib.bsu.by/handle/123456789/10692
Title: Krausz dimension and its generalizations in special graph classes
Authors: Glebova, O. V.
Metelsky, Yu. M.
Skums, P. V.
Issue Date: 2011
Publisher: БГУ
Citation: Международный конгресс по информатике: информационные системы и технологии: материалы международного научного конгресса 31 окт. – 3 нояб. 2011 г. : в 2 ч. Ч. 2. – Минск: БГУ, 2011. – C. 347-350.
Abstract: A krausz (k, m)-partition of a graph G is the partition of G into cliques, such that any vertex belongs to at most k cliques and any two cliques have at most m vertices in common. The m-krausz dimension kdimm(G) of the graph G is the minimum number k such that G has a krausz (k, m)-partition. 1-krausz dimension is known and studied krausz dimension of graph kdim(G). In this paper we prove, that the problem “kdim(G) ≤ 3” is polynomially solvable for chordal graphs, thus partially solving the problem of P. Hlineny and J. Kratochvil. We show, that the problem of finding m-krausz dimension is NP-hard for every m even if restricted to (1, 2)-colorable graphs, but the problem “kdimm(G) ≤ k” is polynomially solvable for (∞, 1)-polar graphs for every fixed k, m ≥ 1.
Description: Секция 10. Теоретическая информатика
URI: http://elib.bsu.by/handle/123456789/10692
ISBN: 978-985-518-564-3
Appears in Collections:2011. Международный конгресс по информатике : информационные системы и технологии. Часть 2.

Files in This Item:
File Description SizeFormat 
75 Glebova.pdf251,43 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.