Parameterizing cut sets in a graph by the number of their components

DOI10.1016/J.TCS.2011.07.005zbMATH Open1232.05115OpenAlexW2074539191MaRDI QIDQ653326FDOQ653326

Authors: Takehiro Ito, Daniël Paulusma, Dimitrios M. Thilikos, Marcin Kamiński 

Publication date: 9 January 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.07.005

Recommendations

• Parameterizing cut sets in a graph by the number of their components
• Minimal disconnected cuts in planar graphs
• Minimal disconnected cuts in planar graphs
• Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems
• On disconnected cuts and separators

zbMATH Keywords

disconnected cut

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Cites Work

• Title not available (Why is that?)
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Graphs on surfaces
• Title not available (Why is that?)
• Title not available (Why is that?)
• A linear time algorithm for finding tree-decompositions of small treewidth
• The Complexity of the List Partition Problem for Graphs
• List Partitions
• Diameter and treewidth in minor-closed graph families
• On stable cutsets in graphs
• FindingH-partitions efficiently
• Computational Complexity of Compaction to Reflexive Cycles
• Contractibility and NP-completeness
• Contraction obstructions for treewidth
• An algorithm for finding clique cut-sets
• Covering graphs with few complete bipartite subgraphs
• Parameterizing cut sets in a graph by the number of their components
• Treewidth reduction for constrained separation and bipartization problems
• Recognizing decomposable graphs
• The computational complexity of disconnected cut and \(2 K_2\)-partition

Cited In (12)

• On the Parameterized Complexity of Cutting a Few Vertices from a Graph
• Disconnected cuts in claw-free graphs
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• Graph minors and parameterized algorithm design
• Reconstructing graphs from cut-set sizes
• Parameterizing cut sets in a graph by the number of their components
• The complexity of contracting bipartite graphs into small cycles
• Parameterized complexity of three edge contraction problems with degree constraints
• Combing a Linkage in an Annulus
• Title not available (Why is that?)
• Minimal disconnected cuts in planar graphs
• Minimal disconnected cuts in planar graphs

This page was built for publication: Parameterizing cut sets in a graph by the number of their components

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