On structural parameterizations of the matching cut problem

DOI10.1007/978-3-319-71147-8_34MaRDI QIDQ1708644zbMATH OpenOpenAlexFDO

Authors N. R. Aravind, Subrahmanyam Kalyanasundaram, Anjeneya Swami Kare

Publication date 26 March 2018

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

zbMATH Keywords

parameterized algorithmdecomposable graphsmatching cut

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Structural and algorithmic properties for parametric minimum cuts
• scientific article; zbMATH DE number 2044946
• A parameterized algorithm for mixed-cut
• scientific article; zbMATH DE number 7650221
• On the complexity of matching cut in graphs of fixed diameter
• An improved parameterized algorithm for the multicut problem
• The perfect matching cut problem revisited
• The perfect matching cut problem revisited
• Matching cutsets in graphs
• A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter

Cited in

(14)

• On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs
• Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
• Speeding up networks mining via neighborhood diversity
• An FPT algorithm for matching cut and d-cut
• Algorithms solving the matching cut problem
• Perfectly matched sets in graphs: parameterized and exact computation
• Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
• Vertex partitioning problems on graphs with bounded tree width
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• The perfect matching cut problem revisited
• The perfect matching cut problem revisited
• Matching cut in graphs with large minimum degree
• scientific article; zbMATH DE number 7378605 (Why is no real title available?)
• scientific article; zbMATH DE number 2084783 (Why is no real title available?)

This page was built for publication: On structural parameterizations of the matching cut problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1708644)