Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms

DOI10.1007/11847250_8zbMath1154.68429OpenAlexW1529906358MaRDI QIDQ3499726

Sing-Hoi Sze, Songjian Lu, Yang Liu, Jian'er Chen

Publication date: 3 June 2008

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11847250_8

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Randomized algorithms (68W20)

Related Items (21)

Mixing Color Coding-Related Techniques ⋮ Parameterized approximation algorithms for packing problems ⋮ A parameterized perspective on packing paths of length two ⋮ A dynamic programming algorithm for tree-like weighted set packing problem ⋮ 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 ⋮ Parameterized exact and approximation algorithms for maximumk-set cover and related satisfiability problems ⋮ Improved Parameterized Algorithms for Weighted 3-Set Packing ⋮ An \(O^{*}(3.53^{3k})\)-time parameterized algorithm for the 3-set packing problem ⋮ Parameterized random complexity ⋮ Packing paths: recycling saves time ⋮ Confronting intractability via parameters ⋮ Parameterized algorithms for weighted matching and packing problems ⋮ Faster fixed-parameter tractable algorithms for matching and packing problems ⋮ Improved deterministic algorithms for weighted matching and packing problems ⋮ Constant ratio fixed-parameter approximation of the edge multicut problem ⋮ The \(k\)-distinct language: parameterized automata constructions ⋮ On problems without polynomial kernels ⋮ On counting 3-D matchings of size \(k\) ⋮ A Parameterized Perspective on Packing Paths of Length Two

This page was built for publication: Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms