Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization

DOI10.1007/s00453-021-00798-8OpenAlexW3131349932MaRDI QIDQ2032346

Ignasi Sau, Guilherme C. M. Gomes

Publication date: 11 June 2021

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1905.03134

zbMATH Keywords

parameterized complexitypolynomial kernelFPT algorithmmatching cutbounded degree cutdistance to cluster

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (5)

Finding matching cuts in \(H\)-free graphs ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ The perfect matching cut problem revisited ⋮ An FPT algorithm for matching cut and d-cut ⋮ (Dis)assortative partitions on random regular graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A fast branching algorithm for cluster vertex deletion
• Fundamentals of parameterized complexity
• Exact exponential algorithms.
• Infeasibility of instance compression and succinct PCPs for NP
• Some consequences of non-uniform conditions on uniform classes
• Algorithms solving the matching cut problem
• On problems without polynomial kernels
• Treewidth. Computations and approximations
• On stable cutsets in line graphs
• On structural parameterizations of the matching cut problem
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Internal Partitions of Regular Graphs
• Finding small separators in linear time via treewidth reduction
• Recognizing decomposable graphs
• The complexity of the matching-cut problem for planar graphs and other graph classes
• Graph decomposition with constraints on the connectivity and minimum degree
• Graph minors. II. Algorithmic aspects of tree-width
• On decomposition of triangle-free graphs under degree constraints
• Kernelization
• Matching cutsets in graphs
• Decomposing C₄‐free graphs under degree constraints
• Parameterized Algorithms
• ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
• On the complexity of \(k\)-SAT

This page was built for publication: Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization