Algorithms solving the matching cut problem
DOI10.1016/J.TCS.2015.10.016zbMATH Open1331.68109OpenAlexW2190210389MaRDI QIDQ897900FDOQ897900
Publication date: 8 December 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2015.10.016
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Fundamentals of parameterized complexity
- Exact exponential algorithms.
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Which problems have strongly exponential complexity?
- Parametrized complexity theory.
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the Complexity of Timetable and Multicommodity Flow Problems
- A Computing Procedure for Quantification Theory
- Finding a Minimum Circuit in a Graph
- On stable cutsets in graphs
- Title not available (Why is that?)
- Matching cutsets in graphs
- On stable cutsets in line graphs
- The complexity of the matching-cut problem for planar graphs and other graph classes
- ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
- Graph decomposition of slim graphs
- Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) Time
- Recognizing decomposable graphs
- Matching cutsets in graphs of diameter 2
- A note on fragile graphs
- On stable cutsets in claw-free graphs and planar graphs
- Title not available (Why is that?)
- Coloring graphs with stable cutsets
- Networks immune to isolated line failures
- Stable set bonding in perfect graphs and parity graphs
- Extremal graphs having no stable cutset
- Algorithms Solving the Matching Cut Problem
- Fragile graphs with small independent cuts
Cited In (23)
- Algorithms Solving the Matching Cut Problem
- Vertex partitioning problems on graphs with bounded tree width
- Title not available (Why is that?)
- A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
- Cutting Barnette graphs perfectly is hard
- Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
- Title not available (Why is that?)
- On conflict-free cuts: algorithms and complexity
- Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
- Dichotomies for maximum matching cut: \(H\)-freeness, bounded diameter, bounded radius
- The perfect matching cut problem revisited
- The perfect matching cut problem revisited
- \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs
- Perfect matching cuts partitioning a graph into complementary subgraphs
- Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization
- Complexity Results for Matching Cut Problems in Graphs Without Long Induced Paths
- Title not available (Why is that?)
- Perfectly matched sets in graphs: parameterized and exact computation
- On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs
- An FPT algorithm for matching cut and d-cut
- Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
- Matching cut in graphs with large minimum degree
- Finding matching cuts in \(H\)-free graphs
This page was built for publication: Algorithms solving the matching cut problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897900)
