Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization

DOI10.4230/LIPIcs.IPEC.2019.19OpenAlexW2998050277MaRDI QIDQ5875553

Unnamed Author, Ignasi Sau

Publication date: 3 February 2023

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/11480/pdf/LIPIcs-IPEC-2019-19.pdf/

zbMATH Keywords

parameterized complexitypolynomial kernelFPT algorithmmatching cutbounded degree cutdistance to cluster

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (6)

Vertex partitioning problems on graphs with bounded tree width ⋮ Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms ⋮ Perfectly matched sets in graphs: parameterized and exact computation ⋮ Refined notions of parameterized enumeration kernels with applications to matching cut enumeration ⋮ The perfect matching cut problem revisited ⋮ Matching cut in graphs with large minimum degree

This page was built for publication: Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization