Algorithms solving the matching cut problem

DOI10.1016/J.TCS.2015.10.016zbMath1331.68109OpenAlexW2190210389MaRDI QIDQ897900

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

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) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (15)

Vertex partitioning problems on graphs with bounded tree width ⋮ Perfect matching cuts partitioning a graph into complementary subgraphs ⋮ Finding matching cuts in \(H\)-free graphs ⋮ Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms ⋮ \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs ⋮ Unnamed Item ⋮ Perfectly matched sets in graphs: parameterized and exact computation ⋮ A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter ⋮ 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Exact exponential algorithms.
• On stable cutsets in claw-free graphs and planar graphs
• Matching cutsets in graphs of diameter 2
• Coloring graphs with stable cutsets
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Graph decomposition of slim graphs
• Stable set bonding in perfect graphs and parity graphs
• On stable cutsets in line graphs
• On stable cutsets in graphs
• A note on fragile graphs
• Which problems have strongly exponential complexity?
• Extremal graphs having no stable cutset
• Parametrized complexity theory.
• Algorithms Solving the Matching Cut Problem
• Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) Time
• Recognizing decomposable graphs
• 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
• Finding a Minimum Circuit in a Graph
• Fragile graphs with small independent cuts
• Matching cutsets in graphs
• A Computing Procedure for Quantification Theory
• ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS

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