The perfect matching cut problem revisited

DOI10.1007/978-3-030-86838-3_14OpenAlexW3204321200MaRDI QIDQ5925551

Jan Arne Telle, Van Bang Le

Publication date: 8 June 2022

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2107.06399

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Parameterized complexity of perfectly matched sets, The perfect matching cut problem revisited

Cites Work

• Unnamed Item
• Graph classes with structured neighborhoods and algorithmic applications
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Exact exponential algorithms.
• Algorithms solving the matching cut problem
• Which problems have strongly exponential complexity?
• A width parameter useful for chordal and co-comparability graphs
• On structural parameterizations of the matching cut problem
• A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
• Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
• An FPT algorithm for matching cut and d-cut
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
• Recognizing decomposable graphs
• The complexity of the matching-cut problem for planar graphs and other graph classes
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Matching cutsets in graphs
• ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
• Matching cut in graphs with large minimum degree
• On the complexity of \(k\)-SAT