Representative families: a unified tradeoff-based approach

DOI10.1016/j.jcss.2015.11.008zbMath1333.68266OpenAlexW2196811896MaRDI QIDQ899582

Hadas Shachnai, Meirav Zehavi

Publication date: 30 December 2015

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2015.11.008

zbMATH Keywords

parameterized algorithmrepresentative family\(k\)-internal out-branchinguniform matroid\(k\)-partial cover

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items (13)

Finding Two Edge-Disjoint Paths with Length Constraints ⋮ A multivariate framework for weighted FPT algorithms ⋮ Balanced substructures in bicolored graphs ⋮ Revisiting the parameterized complexity of maximum-duo preservation string mapping ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Parameterized algorithms for list \(K\)-cycle ⋮ Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials ⋮ Faster deterministic parameterized algorithm for \(k\)-path ⋮ On the complexity of finding internally vertex-disjoint long directed paths ⋮ Long directed \((s,t)\)-path: FPT algorithm ⋮ Approximate Counting of k-Paths: Deterministic and in Polynomial Space ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Two edge-disjoint paths with length constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Spanning trees: A survey
• Parameterized coloring problems on chordal graphs
• Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
• Computing small partial coverings
• A parameterized view on matroid optimization problems
• Minimum leaf out-branching and related problems
• A linear vertex kernel for maximum internal spanning tree
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• Subexponential algorithms for partial cover problems
• Sharp separation and applications to exact and parameterized algorithms
• Algorithms for k-Internal Out-Branching
• Representative Sets of Product Families
• Deterministic Parameterized Algorithms for the Graph Motif Problem
• Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets
• Spotting Trees with Few Leaves
• A 2k-vertex Kernel for Maximum Internal Spanning Tree
• Mixing Color Coding-Related Techniques
• Limits and Applications of Group Algebras for Parameterized Problems
• Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
• Partial vs. Complete Domination: t-Dominating Set
• On generalized graphs

This page was built for publication: Representative families: a unified tradeoff-based approach