An FPT algorithm for matching cut and d-cut
From MaRDI portal
Publication:2115892
DOI10.1007/978-3-030-79987-8_37OpenAlexW3184379502MaRDI QIDQ2115892FDOQ2115892
Authors: N. R. Aravind, Roopam Saxena 
Publication date: 22 March 2022
Full work available at URL: https://arxiv.org/abs/2101.06998
Cites Work
- 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
- On the complexity of matching cut in 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)
