Logo BSU

Please use this identifier to cite or link to this item: https://elib.bsu.by/handle/123456789/10691
Title: Computational complexity of maximum distance-(k, l) matchings in graphs
Authors: Brauner, N.
Finke, G.
Jost, V.
Kovalyov, M. V.
Orlovich, Yu. L.
Pronin, Ph. V.
Waserhole, A.
Keywords: ЭБ БГУ::ОБЩЕСТВЕННЫЕ НАУКИ::Информатика
Issue Date: 2011
Publisher: БГУ
Citation: Международный конгресс по информатике: информационные системы и технологии: материалы международного научного конгресса 31 окт. – 3 нояб. 2011 г. : в 2 ч. Ч. 2. – Минск: БГУ, 2011. – C. 341-346.
Abstract: In this paper, we introduce the concept of a distance-(k, l) matching of a graph, which is a subset of edges of this graph such that the number of intermediate edges in the shortest path between any two edges of this set lies between k and l. We prove that the problem MAXIMUM DISTANCE-(k, l) MATCHING, which asks whether a graph contains a distance-(k, l) matching of size exceeding a given number, is NP-complete for arbitrary given or variable k and l, and that the weighted variant of this problem is strongly NP-complete even for bipartite graphs. We also present several upper bounds on the size of a maximum distance-(k, l) matching.
Description: Секция 10. Теоретическая информатика
URI: http://elib.bsu.by/handle/123456789/10691
ISBN: 978-985-518-564-3
Appears in Collections:2011. Международный конгресс по информатике : информационные системы и технологии. Часть 2.
Статьи факультета прикладной математики и информатики

Files in This Item:
File Description SizeFormat 
74 Brauner.pdf234,05 kBAdobe PDFView/Open


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