On conflict-free cuts: algorithms and complexity
From MaRDI portal
Publication:6602320
DOI10.1016/j.ipl.2024.106503zbMATH Open1547.68633MaRDI QIDQ6602320
Johannes Rauch, Dieter Rautenbach, Uéverton S. Souza
Publication date: 11 September 2024
Published in: Information Processing Letters (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Unnamed Item
- The minimum spanning tree problem with conflict constraints and its variations
- Paths, trees and matchings under disjunctive constraints
- Algorithms solving the matching cut problem
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Which problems have strongly exponential complexity?
- Heuristics and lower bounds for the bin packing problem with conflicts
- Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
- Hitting forbidden subgraphs in graphs of bounded treewidth
- Parametrized complexity theory.
- Extremal graphs having no matching cuts
- The Knapsack Problem with Conflict Graphs
- Recognizing decomposable graphs
- An improved exponential-time algorithm for k -SAT
- The complexity of the matching-cut problem for planar graphs and other graph classes
- A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
- A full derandomization of schöning's k-SAT algorithm
- Parameterized complexity of conflict-free set cover
- On the complexity of \(k\)-SAT
- On conflict-free spanning tree: algorithms and complexity
- Exact and Parameterized Algorithms for the Independent Cutset Problem
- Conflict-free hypergraph matchings
This page was built for publication: On conflict-free cuts: algorithms and complexity
