Conflict free version of covering problems on graphs: classical and parameterized
From MaRDI portal
Publication:5918906
DOI10.1007/s00224-019-09964-6zbMath1453.68136OpenAlexW3008279586MaRDI QIDQ5918906
Pallavi Jain, Lawqueen Kanesh, Pranabendu Misra
Publication date: 26 August 2020
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-019-09964-6
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (3)
Parameterized complexity of \(d\)-hitting set with quotas ⋮ Constrained hitting set problem with intervals ⋮ Parameterized complexity of conflict-free set cover
Cites Work
- Unnamed Item
- Chordal editing is fixed-parameter tractable
- The maximum flow problem with disjunctive constraints
- Solving min ones 2-SAT as fast as vertex cover
- Sparsity. Graphs, structures, and algorithms
- Online variable-sized bin packing with conflicts
- Paths, trees and matchings under disjunctive constraints
- On parameterized independent feedback vertex set
- Finding odd cycle transversals.
- Improved upper bounds for vertex cover
- Fréchet distance between a line and avatar point set
- Scheduling with conflicts: Online and offline algorithms
- Improved algorithms for feedback vertex set problems
- Chordal deletion is fixed-parameter tractable
- The node-deletion problem for hereditary properties is NP-complete
- A bounded approximation for the minimum cost 2-sat problem
- A unified approximation algorithm for node-deletion problems
- Fixed-parameter tractability of graph modification problems for hereditary properties
- \textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms
- Approximation of knapsack problems with conflict and forcing graphs
- Exact algorithms for maximum independent set
- Faster deterministic \textsc{Feedback Vertex Set}
- Fixed-parameter tractability results for feedback set problems in tournaments
- On nowhere dense graphs
- The Maximum Flow Problem with Conflict and Forcing Conditions
- Choice Is Hard
- Determining a Minimum Spanning Tree with Disjunctive Constraints
- On the hardness of approximating minimization problems
- Linear Recognition of Almost Interval Graphs
- Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms
- Polynomially bounded minimization problems which are hard to approximate
- Kernelization
- Interval Deletion Is Fixed-Parameter Tractable
- Node-and edge-deletion NP-complete problems
- Parameterized Algorithms
- The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
This page was built for publication: Conflict free version of covering problems on graphs: classical and parameterized
