Faster fixed-parameter tractable algorithms for matching and packing problems

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

Dimitrios M. Thilikos, Frances A. Rosamond, Ulrike Stege, Christian Knauer, Naomi Nishimura, Michael R. Fellows, 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 packinggraph matchingparameterized complexityfixed parameter tractablecolor coding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (24)

Edge-disjoint packing of stars and cycles ⋮ Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability ⋮ Mixing Color Coding-Related Techniques ⋮ Parameterized approximation algorithms for packing problems ⋮ Complexity results for rainbow matchings ⋮ A dynamic programming algorithm for tree-like weighted set packing problem ⋮ Edge-Disjoint Packing of Stars and Cycles ⋮ Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets ⋮ Narrow sieves for parameterized paths and packings ⋮ The control complexity of \(r\)-Approval: from the single-peaked case to the general case ⋮ Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover} ⋮ Kernelization Algorithms for Packing Problems Allowing Overlaps ⋮ Packing arc-disjoint cycles in oriented graphs ⋮ Confronting intractability via parameters ⋮ Parameterized complexity of induced graph matching on claw-free graphs ⋮ Maximum disjoint paths on edge-colored graphs: approximability and tractability ⋮ On the complexity of broadcast domination and multipacking In digraphs ⋮ Improved deterministic algorithms for weighted matching and packing problems ⋮ A Problem Kernelization for Graph Packing ⋮ The \(k\)-distinct language: parameterized automata constructions ⋮ Parameterized complexity of geometric covering problems having conflicts ⋮ Using Parametric Transformations Toward Polynomial Kernels for Packing Problems Allowing Overlaps ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized complexity of constraint satisfaction problems
• A faster parameterized algorithm for set packing
• Structure preserving reductions among convex optimization problems
• Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
• Divide-and-Color
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Color-coding
• An efficient parameterized algorithm for m-set packing
• Algorithms – ESA 2004
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Faster fixed-parameter tractable algorithms for matching and packing problems