Parameterized algorithms and kernels for rainbow matching

DOI10.1007/s00453-018-0497-3zbMath1422.68188MaRDI QIDQ1739114

Meirav Zehavi, Saket Saurabh, Sushmita Gupta, Sanjukta Roy

Publication date: 25 April 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8124/

zbMATH Keywords

divide-and-conquer; 3-dimensional matching; parameterized algorithm; rainbow matching; 3-set packing; bounded search trees

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)