An FPT algorithm for matching cut and d-cut

DOI10.1007/978-3-030-79987-8_37OpenAlexW3184379502MaRDI QIDQ2115892

Roopam Saxena, N. R. Aravind

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

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

Related Items (4)

Finding matching cuts in \(H\)-free graphs ⋮ The perfect matching cut problem revisited ⋮ The perfect matching cut problem revisited ⋮ On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs

Cites Work

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

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