Matching cut in graphs with large minimum degree
From MaRDI portal
Publication:5925521
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
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