Matching cut in graphs with large minimum degree

DOI10.1007/s00453-020-00782-8MaRDI QIDQ5925521

Sheng-Lung Peng, Van Bang Le, Chi-Yeh Chen, Sun-Yuan Hsieh, Hoàng-Oanh Le

Publication date: 19 April 2021

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-020-00782-8

zbMATH Keywords

graph algorithm; NP-hard problem; matching cut; exact branching algorithm

Mathematics Subject Classification ID

68Wxx: Algorithms in computer science

05Cxx: Graph theory

Related Items

The perfect matching cut problem revisited, The perfect matching cut problem revisited, Parameterized complexity of perfectly matched sets, Finding matching cuts in \(H\)-free graphs, Finding perfect matching cuts faster, On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs, A note on matching-cut in \(P_t\)-free graphs

Cites Work

• Unnamed Item
• Exact exponential algorithms.
• Algorithms solving the matching cut problem
• Matching cutsets in graphs of diameter 2
• On stable cutsets in line graphs
• Forbidden subgraph decomposition
• Which problems have strongly exponential complexity?
• On structural parameterizations of the matching cut problem
• A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• Partition into triangles on bounded degree graphs
• Recognizing decomposable graphs
• The complexity of the matching-cut problem for planar graphs and other graph classes
• Networks immune to isolated line failures
• Matching cutsets in graphs
• 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
• On the complexity of \(k\)-SAT