On conflict-free cuts: algorithms and complexity
type: Item
instance of: scholarly article
title: On conflict-free cuts: algorithms and complexity
zbMATH Open document ID: 1547.68633
author: Johannes Rauch
author: Dieter Rautenbach
author: Uéverton S. Souza
published in: Information Processing Letters
publication date: 2024-09-11T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q27
zbMATH DE Number: 7910939
zbMATH Keywords: conflict-free cut
zbMATH Keywords: graph algorithms
zbMATH Keywords: computational complexity
MaRDI profile type: Publication
cites work: A linear-time algorithm for testing the truth of certain quantified Boolean formulas
cites work: On conflict-free spanning tree: algorithms and complexity
cites work: A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
cites work: The complexity of the matching-cut problem for planar graphs and other graph classes
cites work: Extremal graphs having no matching cuts
cites work: Recognizing decomposable graphs
cites work: Q4385531
cites work: Hitting forbidden subgraphs in graphs of bounded treewidth
cites work: Paths, trees and matchings under disjunctive constraints
cites work: Parametrized complexity theory.
cites work: Heuristics and lower bounds for the bin packing problem with conflicts
cites work: Conflict-free hypergraph matchings
cites work: Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
cites work: On the complexity of \(k\)-SAT
cites work: Which problems have strongly exponential complexity?
cites work: Parameterized complexity of conflict-free set cover
cites work: Algorithms solving the matching cut problem
cites work: A full derandomization of schöning's k-SAT algorithm
cites work: An improved exponential-time algorithm for k -SAT
cites work: The Knapsack Problem with Conflict Graphs
cites work: Exact and Parameterized Algorithms for the Independent Cutset Problem
cites work: The minimum spanning tree problem with conflict constraints and its variations
DOI: 10.1016/J.IPL.2024.106503
description: scientific article; zbMATH DE number 7910939