scientific article; zbMATH DE number 2044946

MaRDI QIDQ4448767zbMATH OpenFDO

Authors Maurizio Patrignani, Maurizio Pizzonia

Publication date 18 February 2004

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:

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