Complexity Results for Matching Cut Problems in Graphs Without Long Induced Paths
- 23 September 2023
- book chapter
- Published by Springer Nature
- p. 417-431
Abstract
No abstract availableKeywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Matching Cut in Graphs with Large Minimum DegreeAlgorithmica, 2020
- A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameterTheoretical Computer Science, 2019
- Algorithms solving the Matching Cut problemTheoretical Computer Science, 2016
- On Promise Problems: A Survey2006
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- On the Complexity of k-SATJournal of Computer and System Sciences, 2001
- Matching cutsets in graphsJournal of Graph Theory, 1989
- Recognizing decomposable graphsJournal of Graph Theory, 1984
- An O(v|v| c |E|) algoithm for finding maximum matching in general graphs1980
- ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTSAnnals of the New York Academy of Sciences, 1970