The sandwich problem for cutsets: clique cutset, \(k\)-star cutset

DOI10.1016/j.dam.2006.03.023zbMath1097.05029OpenAlexW1999061086MaRDI QIDQ2500527

Rafael B. Teixeira, Celina M. Herrera de Figueiredo

Publication date: 17 August 2006

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.03.023

zbMATH Keywords

graph algorithmsrecognition problemsandwich problemsanalysis of algorithms and problem complexityvertex cutsets

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (8)

The polynomial dichotomy for three nonempty part sandwich problems ⋮ The polynomial dichotomy for three nonempty part sandwich problems ⋮ The external constraint 4 nonempty part sandwich problem ⋮ The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory ⋮ The sandwich problem for decompositions and almost monotone properties ⋮ The graph sandwich problem for \(P_4\)-sparse graphs ⋮ Skew partition sandwich problem is NP-complete

Cites Work

• The homogeneous set sandwich problem
• Decomposition by clique separators
• Star-cutsets and perfect graphs
• An algorithm for finding clique cut-sets
• Complexity and algorithms for graph and hypergraph sandwich problems
• Bounded degree interval sandwich problems
• Matrix sandwich problems
• On stable cutsets in graphs
• The graph sandwich problem for 1-join composition is NP-complete
• On decision and optimization (\(k\),\(l\))-graph sandwich problems
• Graph Sandwich Problems
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The sandwich problem for cutsets: clique cutset, \(k\)-star cutset