Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
type: Item
instance of: scholarly article
title: Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
zbMATH Open document ID: 1442.05224
author: Christian Komusiewicz
author: Dieter Kratsch
author: Van Bang Le
published in: Discrete Applied Mathematics
publication date: 2020-06-29T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10220/
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7215464
zbMATH Keywords: NP-hard problem
zbMATH Keywords: kernelization
zbMATH Keywords: branching algorithm
MaRDI profile type: Publication
OpenAlex ID: W2998596251
Wikidata QID: Q115577868
cites work: Good edge-labelling of graphs
cites work: On structural parameterizations of the matching cut problem
cites work: A linear-time algorithm for testing the truth of certain quantified Boolean formulas
cites work: Kernelization Lower Bounds by Cross-Composition
cites work: The complexity of the matching-cut problem for planar graphs and other graph classes
cites work: A fast branching algorithm for cluster vertex deletion
cites work: Matching cutsets in graphs of diameter 2
cites work: Recognizing decomposable graphs
cites work: Parameterized Algorithms
cites work: A Computing Procedure for Quantification Theory
cites work: Fundamentals of parameterized complexity
cites work: On the Complexity of Timetable and Multicommodity Flow Problems
cites work: Networks immune to isolated line failures
cites work: Exact exponential algorithms.
cites work: Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization
cites work: ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
cites work: 3-SAT Faster and Simpler---Unique-SAT Bounds for PPSZ Hold in General
cites work: Matching cut in graphs with large minimum degree
cites work: Algorithms solving the matching cut problem
cites work: A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
cites work: On stable cutsets in line graphs
cites work: Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT
cites work: Finding small separators in linear time via treewidth reduction
cites work: Matching cutsets in graphs
cites work: Q4448767
cites work: An improved exponential-time algorithm for k -SAT
DOI: 10.1016/J.DAM.2019.12.010
description: scientific article