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

DOI10.1016/J.DAM.2006.03.023MaRDI QIDQ2500527zbMATH OpenOpenAlexFDO

Authors R. B. Teixeira, Celina M. H. 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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Skew partition sandwich problem is NP-complete
• scientific article; zbMATH DE number 6423755
• The sandwich problem for decompositions and almost monotone properties
• Graph Sandwich Problems
• On decision and optimization (\(k\),\(l\))-graph sandwich problems

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1161313 (Why is no real title available?)
• scientific article; zbMATH DE number 1953085 (Why is no real title available?)
• scientific article; zbMATH DE number 2079402 (Why is no real title available?)
• An algorithm for finding clique cut-sets
• Bounded degree interval sandwich problems
• Complexity and algorithms for graph and hypergraph sandwich problems
• Decomposition by clique separators
• Graph Sandwich Problems
• Matrix sandwich problems
• On decision and optimization (\(k\),\(l\))-graph sandwich problems
• On stable cutsets in graphs
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• Star-cutsets and perfect graphs
• The graph sandwich problem for 1-join composition is NP-complete
• The homogeneous set sandwich problem

Cited in

(8)

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

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

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