
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Parameterized Algorithms for Disjoint Matchings in Weighted Graphs with Applications
ZhiZhong CHEN Tatsuie TSUKIJI Hiroki YAMADA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E99A
No.6
pp.10501058 Publication Date: 2016/06/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E99.A.1050
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: fixedparameter algorithms, randomized algorithms, matchings, colorcoding, universal sets,
Full Text: PDF(763.9KB) >>Buy this Article
Summary:
It is a wellknown and useful problem to find a matching in a given graph G whose size is at most a given parameter k and whose weight is maximized (over all matchings of size at most k in G). In this paper, we consider two natural extensions of this problem. One is to find t disjoint matchings in a given graph G whose total size is at most a given parameter k and whose total weight is maximized, where t is a (small) constant integer. Previously, only the special case where t=2 was known to be fixedparameter tractable. In this paper, we show that the problem is fixedparameter tractable for any constant t. When t=2, the time complexity of the new algorithm is significantly better than that of the previously known algorithm. The other is to find a set of vertexdisjoint paths each of length 1 or 2 in a given graph whose total length is at most a given parameter k and whose total weight is maximized. As interesting applications, we further use the algorithms to speed up several known approximation algorithms (for related NPhard problems) whose approximation ratio depends on a fixed parameter 0<ε<1 and whose running time is dominated by the time needed for exactly solving the problems on graphs in which each connected component has at most ε^{1} vertices.

