Skew partition sandwich problem is NP-complete
From MaRDI portal
Publication:2840508
DOI10.1016/J.ENDM.2009.11.003zbMATH Open1268.05212OpenAlexW2000021921MaRDI QIDQ2840508FDOQ2840508
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
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
- Title not available (Why is that?)
- Normal hypergraphs and the perfect graph conjecture
- Graph Sandwich Problems
- Decomposing Berge graphs and detecting balanced skew partitions
- The strong perfect graph theorem
- The homogeneous set sandwich problem
- Star-cutsets and perfect graphs
- Fast Skew Partition Recognition
- An algorithm for finding clique cut-sets
- The sandwich problem for cutsets: clique cutset, \(k\)-star cutset
- Title not available (Why is that?)
- The polynomial dichotomy for three nonempty part sandwich problems
- Skew partitions in perfect graphs
Cited In (6)
- 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 P versus NP-complete dichotomy of some challenging problems in graph theory
- The external constraint 4 nonempty part sandwich problem
- The sandwich problem for cutsets: clique cutset, \(k\)-star cutset
- The sandwich problem for decompositions and almost monotone properties
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)
