Mixing Color Coding-Related Techniques
From MaRDI portal
Abstract: Narrow sieves, representative sets and divide-and-color are three breakthrough color coding-related techniques, which led to the design of extremely fast parameterized algorithms. We present a novel family of strategies for applying mixtures of them. This includes: (a) a mix of representative sets and narrow sieves; (b) a faster computation of representative sets under certain separateness conditions, mixed with divide-and-color and a new technique, "balanced cutting"; (c) two mixtures of representative sets, iterative compression and a new technique, "unbalanced cutting". We demonstrate our strategies by obtaining, among other results, significantly faster algorithms for -Internal Out-Branching and Weighted 3-Set -Packing, and a framework for speeding-up the previous best deterministic algorithms for -Path, -Tree, -Dimensional -Matching, Graph Motif and Partial Cover.
Recommendations
Cites work
- scientific article; zbMATH DE number 6687769 (Why is no real title available?)
- scientific article; zbMATH DE number 3974318 (Why is no real title available?)
- scientific article; zbMATH DE number 1261820 (Why is no real title available?)
- A 2k-vertex kernel for maximum internal spanning tree
- A faster parameterized algorithm for set packing
- A linear vertex kernel for maximum internal spanning tree
- A parameterized view on matroid optimization problems
- Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
- Algorithms for k-internal out-branching
- An O *(3.523k ) Parameterized Algorithm for 3-Set Packing
- Color-coding
- Deterministic parameterized algorithms for the graph motif problem
- Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
- Faster Algebraic Algorithms for Path and Packing Problems
- Faster fixed-parameter tractable algorithms for matching and packing problems
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
- Improved Parameterized Algorithms for Weighted 3-Set Packing
- Improved deterministic algorithms for weighted matching and packing problems
- Limits and Applications of Group Algebras for Parameterized Problems
- Minimum leaf out-branching and related problems
- Mixing Color Coding-Related Techniques
- Narrow sieves for parameterized paths and packings
- On generalized graphs
- Parameterized algorithms for module motif
- Parameterized coloring problems on chordal graphs
- Randomized divide-and-conquer: improved path, matching, and packing algorithms
- Reducing to independent set structure -- the case of \(k\)-internal spanning tree
- Representative families: a unified tradeoff-based approach
- Representative sets of product families
- Sharp separation and applications to exact and parameterized algorithms
- Using nondeterminism to design efficient deterministic algorithms
Cited in
(35)- Tight bounds for chordal/interval vertex deletion parameterized by treewidth
- A randomized algorithm for long directed cycle
- Parameterized approximation algorithms for packing problems
- Two edge-disjoint paths with length constraints
- Approximate Counting of k-Paths: Deterministic and in Polynomial Space
- On kernels for \(d\)-path vertex cover
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- Parameterized algorithms and kernels for rainbow matching
- A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families
- Fixed-parameter tractability of maximum colored path and beyond
- Parameterized Algorithms and Kernels for Rainbow Matching
- Patching colors with tensors
- Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials
- A note on algebraic techniques for subgraph detection
- Faster deterministic parameterized algorithm for k-path
- Spotting trees with few leaves
- Forgetfulness can make you faster: an O^*(8.097ᵏ)-time algorithm for weighted 3-set k-packing
- Representative families for matroid intersections, with applications to location, packing, and covering problems
- Counting connected subgraphs with maximum-degree-aware sieving
- Narrow sieves for parameterized paths and packings
- On the descriptive complexity of color coding
- Parameterized analysis and crossing minimization problems
- Long directed \((s,t)\)-path: FPT algorithm
- Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
- Discriminantal subset convolution: refining exterior-algebraic methods for parameterized algorithms
- Finding two edge-disjoint paths with length constraints
- Finding detours is fixed-parameter tractable
- Mixing Color Coding-Related Techniques
- A multivariate approach for weighted FPT algorithms
- A faster FPT algorithm for 3-path vertex cover
- Parameterized algorithms for list \(K\)-cycle
- Representative families: a unified tradeoff-based approach
- Adaptive multicolouring
- Advanced Screen Content Coding Using Color Table and Index Map
- Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs
This page was built for publication: Mixing Color Coding-Related Techniques
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452864)
