Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
From MaRDI portal
Publication:2192064
DOI10.1016/j.dam.2019.12.010zbMath1442.05224OpenAlexW2998596251WikidataQ115577868 ScholiaQ115577868MaRDI QIDQ2192064
Dieter Kratsch, Van Bang Le, Christian Komusiewicz
Publication date: 29 June 2020
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10220/
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (12)
Vertex partitioning problems on graphs with bounded tree width ⋮ Finding matching cuts in \(H\)-free graphs ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ FPT and kernelization algorithms for the induced tree problem ⋮ Perfectly matched sets in graphs: parameterized and exact computation ⋮ Refined notions of parameterized enumeration kernels with applications to matching cut enumeration ⋮ Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization ⋮ The perfect matching cut problem revisited ⋮ The perfect matching cut problem revisited ⋮ Matching cut in graphs with large minimum degree ⋮ On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs ⋮ An FPT algorithm for matching cut and d-cut
Cites Work
- Unnamed Item
- A fast branching algorithm for cluster vertex deletion
- Fundamentals of parameterized complexity
- Exact exponential algorithms.
- Algorithms solving the matching cut problem
- Matching cutsets in graphs of diameter 2
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- On stable cutsets in line graphs
- On structural parameterizations of the matching cut problem
- A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
- Finding small separators in linear time via treewidth reduction
- Recognizing decomposable graphs
- An improved exponential-time algorithm for k -SAT
- The complexity of the matching-cut problem for planar graphs and other graph classes
- Networks immune to isolated line failures
- On the Complexity of Timetable and Multicommodity Flow Problems
- Kernelization Lower Bounds by Cross-Composition
- Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT
- Matching cutsets in graphs
- 3-SAT Faster and Simpler---Unique-SAT Bounds for PPSZ Hold in General
- Parameterized Algorithms
- A Computing Procedure for Quantification Theory
- ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
- Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization
- Good edge-labelling of graphs
- Matching cut in graphs with large minimum degree
This page was built for publication: Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
