Parameterized complexity of conflict-free set cover

DOI10.1007/s00224-020-10022-9OpenAlexW3119713976MaRDI QIDQ5918356

Ashwin Jacob, Venkatesh Raman, Diptapriyo Majumdar

Publication date: 3 August 2021

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-020-10022-9

zbMATH Keywords

fixed parameter tractabilityset coverparameterized complexityW-hardness

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Computing methodologies and applications (68Uxx) Extremal combinatorics (05Dxx)

Related Items (1)

Constrained hitting set problem with intervals

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Online variable-sized bin packing with conflicts
• Paths, trees and matchings under disjunctive constraints
• Fréchet distance between a line and avatar point set
• Scheduling with conflicts: Online and offline algorithms
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• A parameterized view on matroid optimization problems
• On generating all maximal independent sets
• On diameters and radii of bridged graphs
• Treewidth. Computations and approximations
• Which problems have strongly exponential complexity?
• Selecting and covering colored points
• Algorithmic graph theory and perfect graphs
• Approximation of knapsack problems with conflict and forcing graphs
• Fixed-parameter algorithms for maximum-profit facility location under matroid constraints
• On nowhere dense graphs
• The Maximum Flow Problem with Conflict and Forcing Conditions
• Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
• Deterministic Truncation of Linear Matroids
• Choice Is Hard
• Minimum-diameter covering problems
• Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms
• Polynomially bounded minimization problems which are hard to approximate
• Constant-Factor Approximations for Asymmetric TSP on Nearly-Embeddable Graphs.
• On Problems as Hard as CNF-SAT
• Parameterized Algorithms
• Graph-Theoretic Concepts in Computer Science
• Slightly Superexponential Parameterized Problems
• Conflict free version of covering problems on graphs: classical and parameterized
• Parameterized complexity of geometric covering problems having conflicts
• Parameterized complexity of conflict-free set cover

This page was built for publication: Parameterized complexity of conflict-free set cover