Parameterized complexity of conflict-free matchings and paths
From MaRDI portal
Publication:2182094
DOI10.1007/s00453-020-00681-yzbMath1442.68072OpenAlexW3006397453MaRDI QIDQ2182094
Saket Saurabh, Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh
Publication date: 21 May 2020
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10979/
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (3)
Constrained hitting set problem with intervals ⋮ Finding temporal paths under waiting time constraints ⋮ Finding Temporal Paths Under Waiting Time Constraints.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- The maximum flow problem with disjunctive constraints
- Fundamentals of parameterized complexity
- Online variable-sized bin packing with conflicts
- On the parameterized complexity of some optimization problems related to multiple-interval graphs
- Paths, trees and matchings under disjunctive constraints
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Scheduling with conflicts: Online and offline algorithms
- A parameterized view on matroid optimization problems
- Treewidth. Computations and approximations
- Heuristics and lower bounds for the bin packing problem with conflicts
- An approximation scheme for bin packing with conflicts
- Approximation of knapsack problems with conflict and forcing graphs
- Parametrized complexity theory.
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- The Maximum Flow Problem with Conflict and Forcing Conditions
- Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
- The Knapsack Problem with Conflict Graphs
- On a routing problem
- Deterministic Truncation of Linear Matroids
- Determining a Minimum Spanning Tree with Disjunctive Constraints
- Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms
- Exploring the Kernelization Borders for Hitting Cycles
- Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
- Multiplying matrices faster than coppersmith-winograd
- Parameterized Algorithms
- Conflict free version of covering problems on graphs: classical and parameterized
This page was built for publication: Parameterized complexity of conflict-free matchings and paths
