Algorithms solving the matching cut problem

DOI10.1016/J.TCS.2015.10.016MaRDI QIDQ897900zbMATHOpenAlexFDO

Authors Dieter Kratsch, Van Bang Le

Publication date 8 December 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.10.016

zbMATH Keywords

graph algorithmmatching cut

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Algorithms Solving the Matching Cut Problem
• scientific article; zbMATH DE number 7378605
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• On structural parameterizations of the matching cut problem
• The complexity of the matching-cut problem for planar graphs and other graph classes (extended abstract)

Cites work

• scientific article; zbMATH DE number 1161313 (Why is no real title available?)
• scientific article; zbMATH DE number 2044946 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A Computing Procedure for Quantification Theory
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A note on fragile graphs
• Algorithms Solving the Matching Cut Problem
• Coloring graphs with stable cutsets
• Exact exponential algorithms.
• Extremal graphs having no stable cutset
• Finding a Minimum Circuit in a Graph
• Fragile graphs with small independent cuts
• Fundamentals of parameterized complexity
• Graph decomposition of slim graphs
• Lower bounds based on the exponential time hypothesis
• Matching cutsets in graphs
• Matching cutsets in graphs of diameter 2
• Min-cuts and shortest cycles in planar graphs in \(O(n \log\log n)\) time
• Networks immune to isolated line failures
• ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
• On stable cutsets in claw-free graphs and planar graphs
• On stable cutsets in graphs
• On stable cutsets in line graphs
• On the Complexity of Timetable and Multicommodity Flow Problems
• Parametrized complexity theory.
• Recognizing decomposable graphs
• Stable set bonding in perfect graphs and parity graphs
• The complexity of the matching-cut problem for planar graphs and other graph classes
• Which problems have strongly exponential complexity?

Cited in

(25)

• The complexity of the matching-cut problem for planar graphs and other graph classes (extended abstract)
• A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
• Complexity Results for Matching Cut Problems in Graphs Without Long Induced Paths
• Cutting Barnette graphs perfectly is hard
• On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs
• On conflict-free cuts: algorithms and complexity
• Dichotomies for maximum matching cut: \(H\)-freeness, bounded diameter, bounded radius
• Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
• scientific article; zbMATH DE number 4197736 (Why is no real title available?)
• Finding matching cuts in \(H\)-free graphs
• An FPT algorithm for matching cut and d-cut
• Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization
• Perfectly matched sets in graphs: parameterized and exact computation
• Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
• Vertex partitioning problems on graphs with bounded tree width
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• The perfect matching cut problem revisited
• The perfect matching cut problem revisited
• The complexity of the matching-cut problem for planar graphs and other graph classes
• Matching cut in graphs with large minimum degree
• Algorithms Solving the Matching Cut Problem
• scientific article; zbMATH DE number 7378605 (Why is no real title available?)
• scientific article; zbMATH DE number 2044946 (Why is no real title available?)
• \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs
• Perfect matching cuts partitioning a graph into complementary subgraphs

This page was built for publication: Algorithms solving the matching cut problem

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