Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
type: Item
instance of: scholarly article
title: Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
author: Guilherme C. M. Gomes
author: Ignasi Sau
published in: Algorithmica
publication date: 2021-06-11T00:00:00Z
full work available at URL: https://arxiv.org/abs/1905.03134
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/11480/
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7357815
zbMATH Keywords: matching cut
zbMATH Keywords: bounded degree cut
zbMATH Keywords: parameterized complexity
zbMATH Keywords: FPT algorithm
zbMATH Keywords: polynomial kernel
zbMATH Keywords: distance to cluster
MaRDI profile type: Publication
OpenAlex ID: W3131349932
cites work: On structural parameterizations of the matching cut problem
cites work: Internal partitions of regular graphs
cites work: On problems without polynomial kernels
cites work: Q3113681
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: Recognizing decomposable graphs
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Parameterized Algorithms
cites work: Q3577833
cites work: Fundamentals of parameterized complexity
cites work: Exact exponential algorithms.
cites work: Kernelization
cites work: Infeasibility of instance compression and succinct PCPs for NP
cites work: ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
cites work: On the complexity of \(k\)-SAT
cites work: On decomposition of triangle-free graphs under degree constraints
cites work: Treewidth. Computations and approximations
cites work: Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
cites work: Algorithms solving the matching cut problem
cites work: Q4636534
cites work: On stable cutsets in line graphs
cites work: Q4083461
cites work: Decomposing C4‐free graphs under degree constraints
cites work: Finding small separators in linear time via treewidth reduction
cites work: Matching cutsets in graphs
cites work: Q4448767
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: Q4405794
cites work: Q4715286
cites work: Graph decomposition with constraints on the connectivity and minimum degree
cites work: Some consequences of non-uniform conditions on uniform classes
DOI: 10.1007/S00453-021-00798-8
description: scientific article; zbMATH DE number 7357815