An FPT algorithm for matching cut and d-cut
type: Item
instance of: scholarly article
title: An FPT algorithm for matching cut and d-cut
DOI: 10.1007/978-3-030-79987-8_37
author: N. R. Aravind
author: Roopam Saxena
publication date: 2022-03-22T00:00:00Z
full work available at URL: https://arxiv.org/abs/2101.06998
Mathematics Subject Classification ID: 68Rxx
Mathematics Subject Classification ID: 68Wxx
zbMATH DE Number: 7495046
zbMATH Keywords: matching cut
zbMATH Keywords: fixed-parameter tractable
zbMATH Keywords: algorithms
MaRDI profile type: Publication
OpenAlex ID: W3184379502
cites work: On structural parameterizations of the matching cut problem
cites work: The complexity of the matching-cut problem for planar graphs and other graph classes
cites work: Designing FPT Algorithms for Cut Problems Using Randomized Contractions
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: Randomized Contractions Meet Lean Decompositions
cites work: Fundamentals of parameterized complexity
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: Matching cut in graphs with large minimum degree
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: A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
cites work: Treewidth reduction for constrained separation and bipartization problems
cites work: A simple min-cut algorithm
description: scientific article; zbMATH DE number 7495046