An FPT algorithm for matching cut and d-cut

DOI10.1007/978-3-030-79987-8_37MaRDI QIDQ2115892zbMATH OpenOpenAlexFDO

Authors N. R. Aravind, Roopam Saxena

Publication date 22 March 2022

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

zbMATH Keywords

algorithmsfixed-parameter tractablematching cut

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cites work

• A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
• A simple min-cut algorithm
• Algorithms solving the matching cut problem
• Designing FPT algorithms for cut problems using randomized contractions
• Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
• Fundamentals of parameterized complexity
• Matching cut in graphs with large minimum degree
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
• On structural parameterizations of the matching cut problem
• On the complexity of matching cut in graphs of fixed diameter
• Parameterized algorithms
• Randomized Contractions Meet Lean Decompositions
• Recognizing decomposable graphs
• The complexity of the matching-cut problem for planar graphs and other graph classes
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Treewidth reduction for constrained separation and bipartization problems

Cited in

(12)

• On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs
• scientific article; zbMATH DE number 7378605 (Why is no real title available?)
• The perfect matching cut problem revisited
• The perfect matching cut problem revisited
• Finding matching cuts in \(H\)-free graphs
• Dichotomies for maximum matching cut: \(H\)-freeness, bounded diameter, bounded radius
• Finding d-cuts in graphs of bounded diameter, graphs of bounded radius and H-free graphs
• Matching cuts in graphs of high girth and H-free graphs
• Matching cuts in graphs of high girth and \(H\)-free graphs
• Finding \(d\)-cuts in graphs of bounded diameter, graphs of bounded radius and \(H\)-free graphs
• Matching (multi)cut: algorithms, complexity, and enumeration
• Finding d-cuts in claw-free graphs

This page was built for publication: An FPT algorithm for matching cut and d-cut

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2115892)