Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints

DOI10.1007/978-3-662-48350-3_46zbMath1432.68193arXiv1411.6756OpenAlexW2140987434MaRDI QIDQ3452817

Daniel Lokshtanov, Michał Pilipczuk, Ariel Gabizon

Publication date: 19 November 2015

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

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

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (5)

Almost Optimal Cover-Free Families ⋮ Kernelization of Cycle Packing with Relaxed Disjointness Constraints ⋮ Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints ⋮ Tight Lower Bounds for the Complexity of Multicoloring ⋮ Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Efficient construction of a small hitting set for combinatorial rectangles in high dimension
• Narrow sieves for parameterized paths and packings
• Sharp separation and applications to exact and parameterized algorithms
• Representative Sets of Product Families
• Representative Families: A Unified Tradeoff-Based Approach
• On r-Simple k-Path
• Deterministic Parameterized Algorithms for the Graph Motif Problem
• Kernelization Algorithms for Packing Problems Allowing Overlaps
• Testers and their applications
• Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints
• Faster Algebraic Algorithms for Path and Packing Problems
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal
• Parameterized Algorithms

This page was built for publication: Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints