Skew partition sandwich problem is NP-complete

DOI10.1016/J.ENDM.2009.11.003MaRDI QIDQ2840508zbMATH OpenOpenAlexFDO

Authors R. B. Teixeira, Simone Dantas, Celina M. H. de Figueiredo

Publication date 19 July 2013

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2009.11.003

zbMATH Keywords

graph theorycomplexitygraph decompositionperfect graphsgraph sandwich problems

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
• The sandwich problem for cutsets: clique cutset, \(k\)-star cutset
• Stable skew partition problem
• The sandwich problem for decompositions and almost monotone properties
• The external constraint 4 nonempty part sandwich problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1512686 (Why is no real title available?)
• An algorithm for finding clique cut-sets
• Decomposing Berge graphs and detecting balanced skew partitions
• Fast Skew Partition Recognition
• Graph Sandwich Problems
• Normal hypergraphs and the perfect graph conjecture
• Skew partitions in perfect graphs
• Star-cutsets and perfect graphs
• The homogeneous set sandwich problem
• The polynomial dichotomy for three nonempty part sandwich problems
• The sandwich problem for cutsets: clique cutset, \(k\)-star cutset
• The strong perfect graph theorem

Cited in

(6)

• 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 graph sandwich problem for 1-join composition is NP-complete
• The sandwich problem for decompositions and almost monotone properties
• The sandwich problem for cutsets: clique cutset, \(k\)-star cutset

This page was built for publication: Skew partition sandwich problem is NP-complete

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