scientific article; zbMATH DE number 7378605

DOI10.4230/LIPICS.IPEC.2018.19MaRDI QIDQ5009482zbMATH OpenFDO

Authors Christian Komusiewicz, Dieter Kratsch, Bang le van

Publication date 4 August 2021

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2018.19

zbMATH Keywords

decomposable graphgraph algorithmmatching cut

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx)

Recommendations

• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
• Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization
• Fast and Deterministic Approximations for k-Cut.
• Fast and deterministic approximations for \(k\)-cut
• An FPT algorithm for matching cut and d-cut
• Linear kernels and linear-time algorithms for finding large cuts
• Linear kernels and linear-time algorithms for finding large cuts
• SOFSEM 2006: Theory and Practice of Computer Science
• \((k,n-k)\)-max-cut: an \({\mathcal O}^*(2^p)\)-time algorithm and a polynomial kernel

Cites work

• A Computing Procedure for Quantification Theory
• A fast branching algorithm for cluster vertex deletion
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Algorithms solving the matching cut problem
• Exact exponential algorithms.
• Good edge-labelling of graphs
• scientific article; zbMATH DE number 2044946 (Why is no real title available?)
• 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 line graphs
• On structural parameterizations of the matching cut problem
• On the complexity of matching cut in graphs of fixed diameter
• On the Complexity of Timetable and Multicommodity Flow Problems
• Parameterized algorithms
• Recognizing decomposable graphs
• The complexity of the matching-cut problem for planar graphs and other graph classes

Cited in

(8)

• Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
• A single exponential-time FPT algorithm for cactus contraction
• 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
• Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization
• Finding perfect matching cuts faster
• Algorithms solving the matching cut problem

This page was built for publication:

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