On conflict-free cuts: algorithms and complexity

DOI10.1016/J.IPL.2024.106503MaRDI QIDQ6602320zbMATH OpenFDO

Authors Johannes Rauch, Dieter Rautenbach, Uéverton S. Souza

Publication date 11 September 2024

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IPL.2024.106503

zbMATH Keywords

computational complexityconflict-free cutgraph algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Parameterized complexity of conflict-free matchings and paths
• Parameterized complexity of conflict-free matchings and paths
• scientific article; zbMATH DE number 2044946
• Conflict free version of covering problems on graphs: classical and parameterized
• Conflict free version of covering problems on graphs: classical and parameterized

Cites work

• A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
• A full derandomization of Schöning's \(k\)-\textsc{SAT} algorithm
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Algorithms solving the matching cut problem
• An improved exponential-time algorithm for k -SAT
• Conflict-free hypergraph matchings
• Exact and Parameterized Algorithms for the Independent Cutset Problem
• Extremal graphs having no matching cuts
• Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
• Heuristics and lower bounds for the bin packing problem with conflicts
• Hitting forbidden subgraphs in graphs of bounded treewidth
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• On conflict-free spanning tree: algorithms and complexity
• On the complexity of k-SAT
• Parameterized complexity of conflict-free set cover
• Parametrized complexity theory.
• Paths, trees and matchings under disjunctive constraints
• Recognizing decomposable graphs
• The complexity of the matching-cut problem for planar graphs and other graph classes
• The Knapsack Problem with Conflict Graphs
• The minimum spanning tree problem with conflict constraints and its variations
• Which problems have strongly exponential complexity?

Cited in

(2)

• Parameterized complexity of conflict-free matchings and paths
• On conflict-free spanning tree: mapping tractable and hard instances through the lenses of graph classes

This page was built for publication: On conflict-free cuts: algorithms and complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6602320)