The complexity of the matching-cut problem

DOI10.1007/3-540-45477-2_26MaRDI QIDQ4448767zbMATH OpenFDO

Authors Maurizio Patrignani, Maurizio Pizzonia

Publication date 18 February 2004

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

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2204/22040284.htm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The complexity of the matching-cut problem for planar graphs and other graph classes (extended abstract)
• The complexity of the matching-cut problem for planar graphs and other graph classes
• Algorithms Solving the Matching Cut Problem
• Algorithms solving the matching cut problem
• Matching cutsets in graphs

Cited in

(41)

• On the complexity of finding balanced oneway cuts
• Complexity of matching problems
• On structural parameterizations of the matching cut problem
• A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
• Surjective \(H\)-colouring: new hardness results
• Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
• Complexity results for two kinds of colored disconnections of graphs
• On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs
• Vertex partitioning problems on graphs with bounded tree width
• Perfect matching cuts partitioning a graph into complementary subgraphs
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• Discontinuities in the complexities of some graph recognition problems
• Combinatorial complexity of a certain 1-dimensional cutting stock problem
• Algorithms Solving the Matching Cut Problem
• Computing vertex-surjective homomorphisms to partially reflexive trees
• The complexity of the matching-cut problem for planar graphs and other graph classes
• On the complexity of matching cut in graphs of fixed diameter
• scientific article; zbMATH DE number 7378605 (Why is no real title available?)
• The complexity of SIMPLE MAX-CUT on comparability graphs
• Matching cutsets in graphs
• scientific article; zbMATH DE number 2230235 (Why is no real title available?)
• The complexity of the matching-cut problem for planar graphs and other graph classes (extended abstract)
• Matching cut in graphs with large minimum degree
• Finding matching cuts in \(H\)-free graphs
• \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs
• Cutting Barnette graphs perfectly is hard
• On conflict-free cuts: algorithms and complexity
• Dichotomies for maximum matching cut: \(H\)-freeness, bounded diameter, bounded radius
• Finding d-cuts in probe H-free graphs
• On cuts and matchings in planar graphs
• Finding d-cuts in graphs of bounded diameter, graphs of bounded radius and H-free graphs
• Matching cuts in graphs of high girth and H-free graphs
• Matching cuts in graphs of high girth and \(H\)-free graphs
• Finding \(d\)-cuts in graphs of bounded diameter, graphs of bounded radius and \(H\)-free graphs
• Perfect matching cuts partitioning a graph into complementary subgraphs
• Computing vertex-surjective homomorphisms to partially reflexive trees
• Matching (multi)cut: algorithms, complexity, and enumeration
• Algorithms solving the matching cut problem
• On stable cutsets in claw-free graphs and planar graphs
• Satisfactory graph partition, variants, and generalizations

This page was built for publication: The complexity of the matching-cut problem

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