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

DOI10.1016/J.TCS.2011.07.005MaRDI QIDQ653326zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

disconnected cut

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(12)

• Parameterized complexity of three edge contraction problems with degree constraints
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• On the Parameterized Complexity of Cutting a Few Vertices from a Graph
• Combing a Linkage in an Annulus
• scientific article; zbMATH DE number 5938876 (Why is no real title available?)
• Disconnected cuts in claw-free graphs
• Graph minors and parameterized algorithm design
• Parameterizing cut sets in a graph by the number of their components
• Minimal disconnected cuts in planar graphs
• The complexity of contracting bipartite graphs into small cycles
• Reconstructing graphs from cut-set sizes
• 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)