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

DOI10.1016/j.tcs.2011.07.005zbMath1232.05115OpenAlexW2074539191MaRDI QIDQ653326

Dimitrios M. Thilikos, Takehiro Ito, Daniël Paulusma, Marcin Kaminski

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)

Related Items

Graph Minors and Parameterized Algorithm Design ⋮ Minimal Disconnected Cuts in Planar Graphs ⋮ Disconnected cuts in claw-free graphs ⋮ The complexity of contracting bipartite graphs into small cycles ⋮ Combing a Linkage in an Annulus ⋮ Parameterized complexity of three edge contraction problems with degree constraints ⋮ The computational complexity of disconnected cut and \(2 K_2\)-partition

Cites Work

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