An FPT algorithm for matching cut and d-cut

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

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)

Cites Work

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

Cited In (6)

• Title not available (Why is that?)
• Dichotomies for maximum matching cut: \(H\)-freeness, bounded diameter, bounded radius
• 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
• Finding matching cuts in \(H\)-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)