Skew partition sandwich problem is NP-complete

DOI10.1016/j.endm.2009.11.003zbMath1268.05212OpenAlexW2000021921MaRDI QIDQ2840508

Simone Dantas, Rafael B. Teixeira, Celina M. Herrera 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

complexitygraph theoryperfect graphsgraph decompositiongraph sandwich problems

Mathematics Subject Classification ID

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

Related Items (3)

The external constraint 4 nonempty part sandwich problem ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory ⋮ The sandwich problem for decompositions and almost monotone properties

Cites Work

• Unnamed Item
• Unnamed Item
• The homogeneous set sandwich problem
• The strong perfect graph theorem
• Star-cutsets and perfect graphs
• An algorithm for finding clique cut-sets
• Decomposing Berge graphs and detecting balanced skew partitions
• Skew partitions in perfect graphs
• The sandwich problem for cutsets: clique cutset, \(k\)-star cutset
• Normal hypergraphs and the perfect graph conjecture
• Graph Sandwich Problems
• Fast Skew Partition Recognition
• The polynomial dichotomy for three nonempty part sandwich problems

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