Mixing Color Coding-Related Techniques

DOI10.1007/978-3-662-48350-3_86zbMath1430.68250arXiv1410.5062OpenAlexW1842913573MaRDI QIDQ3452864

Meirav Zehavi

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1410.5062

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (28)

A randomized algorithm for long directed cycle ⋮ A note on algebraic techniques for subgraph detection ⋮ Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices ⋮ Spotting Trees with Few Leaves ⋮ A Multivariate Approach for Weighted FPT Algorithms ⋮ Mixing Color Coding-Related Techniques ⋮ Parameterized approximation algorithms for packing problems ⋮ Finding Two Edge-Disjoint Paths with Length Constraints ⋮ Narrow sieves for parameterized paths and packings ⋮ Parameterized analysis and crossing minimization problems ⋮ Discriminantal subset convolution: refining exterior-algebraic methods for parameterized algorithms ⋮ Representative families: a unified tradeoff-based approach ⋮ A faster FPT algorithm for 3-path vertex cover ⋮ Parameterized algorithms for list \(K\)-cycle ⋮ Parameterized algorithms and kernels for rainbow matching ⋮ Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials ⋮ Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs ⋮ A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families ⋮ Unnamed Item ⋮ Faster deterministic parameterized algorithm for \(k\)-path ⋮ Unnamed Item ⋮ Representative families for matroid intersections, with applications to location, packing, and covering problems ⋮ Long directed \((s,t)\)-path: FPT algorithm ⋮ Finding Detours is Fixed-Parameter Tractable ⋮ Approximate Counting of k-Paths: Deterministic and in Polynomial Space ⋮ Parameterized Algorithms and Kernels for Rainbow Matching ⋮ Two edge-disjoint paths with length constraints ⋮ Finding, hitting and packing cycles in subexponential time on unit disk graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved deterministic algorithms for weighted matching and packing problems
• Parameterized coloring problems on chordal graphs
• Faster fixed-parameter tractable algorithms for matching and packing problems
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
• A parameterized view on matroid optimization problems
• Minimum leaf out-branching and related problems
• A faster parameterized algorithm for set packing
• Using nondeterminism to design efficient deterministic algorithms
• A linear vertex kernel for maximum internal spanning tree
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• Narrow sieves for parameterized paths and packings
• Sharp separation and applications to exact and parameterized algorithms
• Parameterized Algorithms for Module Motif
• Algorithms for k-Internal Out-Branching
• Representative Sets of Product Families
• Representative Families: A Unified Tradeoff-Based Approach
• Deterministic Parameterized Algorithms for the Graph Motif Problem
• A 2k-vertex Kernel for Maximum Internal Spanning Tree
• Mixing Color Coding-Related Techniques
• Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
• An O *(3.523k ) Parameterized Algorithm for 3-Set Packing
• Improved Parameterized Algorithms for Weighted 3-Set Packing
• Faster Algebraic Algorithms for Path and Packing Problems
• Limits and Applications of Group Algebras for Parameterized Problems
• Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
• Color-coding
• On generalized graphs

This page was built for publication: Mixing Color Coding-Related Techniques