Algorithms Solving the Matching Cut Problem

DOI10.1007/978-3-319-18173-8_21MaRDI QIDQ2947027zbMATH OpenOpenAlexFDO

Authors Dieter Kratsch, Van Bang Le

Publication date 21 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-18173-8_21

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Algorithms solving the matching cut problem
• scientific article; zbMATH DE number 2044946
• The perfect matching cut problem revisited
• The perfect matching cut problem revisited
• Algorithms for cut problems on trees
• scientific article; zbMATH DE number 1064585
• Algorithms for Multiterminal Cuts
• A simple algorithm for the multiway cut problem
• Approximation algorithms for feasible cut and multicut problems
• Algorithms and formulations for the minimum cut separator problem

Cites work

• scientific article; zbMATH DE number 1161313 (Why is no real title available?)
• scientific article; zbMATH DE number 2044946 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A Computing Procedure for Quantification Theory
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A note on fragile graphs
• Coloring graphs with stable cutsets
• Exact exponential algorithms.
• Extremal graphs having no stable cutset
• Finding a Minimum Circuit in a Graph
• Fragile graphs with small independent cuts
• Fundamentals of parameterized complexity
• Graph decomposition of slim graphs
• Matching cutsets in graphs
• Matching cutsets in graphs of diameter 2
• Networks immune to isolated line failures
• ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
• On stable cutsets in claw-free graphs and planar graphs
• On stable cutsets in graphs
• On stable cutsets in line graphs
• On the Complexity of Timetable and Multicommodity Flow Problems
• Parametrized complexity theory.
• Recognizing decomposable graphs
• Stable set bonding in perfect graphs and parity graphs
• The complexity of the matching-cut problem for planar graphs and other graph classes
• Which problems have strongly exponential complexity?

Cited in

(8)

• The complexity of the matching-cut problem for planar graphs and other graph classes (extended abstract)
• Vertex partitioning problems on graphs with bounded tree width
• scientific article; zbMATH DE number 2044946 (Why is no real title available?)
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• The perfect matching cut problem revisited
• Algorithms solving the matching cut problem
• The complexity of the matching-cut problem for planar graphs and other graph classes
• scientific article; zbMATH DE number 4197736 (Why is no real title available?)

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 Q2947027)