Faster fixed-parameter tractable algorithms for matching and packing problems

DOI10.1007/s00453-007-9146-yzbMath1170.68047WikidataQ57359876 ScholiaQ57359876MaRDI QIDQ958209

Michael R. Fellows, Frances A. Rosamond, Dimitrios M. Thilikos, Naomi Nishimura, Christian Knauer, Ulrike Stege, S. H. Whitesides, Prabhakar Ragde

Publication date: 2 December 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9146-y

zbMATH Keywords

set packing; graph matching; parameterized complexity; fixed parameter tractable; color coding

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

68W05: Nonnumerical algorithms

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

05C85: Graph algorithms (graph-theoretic aspects)