The perfect matching cut problem revisited

DOI10.1016/j.tcs.2022.07.035OpenAlexW3179053635MaRDI QIDQ5918785

Jan Arne Telle, Van Bang Le

Publication date: 1 September 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.07.035

zbMATH Keywords

computational complexitygraph algorithmmatching cutexact branching algorithmperfect matching cut

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Finding matching cuts in \(H\)-free graphs ⋮ Finding perfect matching cuts faster

Cites Work

• Unnamed Item
• 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
• 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
• The point-set embeddability problem for plane graphs
• 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
• Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization
• Matching cut in graphs with large minimum degree
• The perfect matching cut problem revisited
• On the complexity of \(k\)-SAT

This page was built for publication: The perfect matching cut problem revisited