Matching cut in graphs with large minimum degree

DOI10.1007/s00453-020-00782-8OpenAlexW3110459966MaRDI 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 algorithmNP-hard problemmatching cutexact branching algorithm

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (7)

Parameterized complexity of perfectly matched sets ⋮ Finding matching cuts in \(H\)-free graphs ⋮ Finding perfect matching cuts faster ⋮ 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 ⋮ 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

This page was built for publication: Matching cut in graphs with large minimum degree