A general method for forbidden induced subgraph sandwich problem NP-completeness

DOI10.1016/j.entcs.2019.08.035OpenAlexW2977429056WikidataQ113317397 ScholiaQ113317397MaRDI QIDQ2132372

Priscila Petito, Simone Dantas, Rafael B. Teixeira, Celina M. Herrera de Figueiredo

Publication date: 27 April 2022

Full work available at URL: https://doi.org/10.1016/j.entcs.2019.08.035

zbMATH Keywords

satisfiabilityforbidden induced subgraphgraph sandwich problems3-\textsc{sat}algorithms and computational complexitylinear CNF-formula

Mathematics Subject Classification ID

Mathematical programming (90Cxx) Graph theory (05Cxx)

Cites Work

• On the forbidden induced subgraph sandwich problem
• Linear CNF formulas and satisfiability
• On the complexity of DNA physical mapping
• Sandwich and probe problems for excluding paths
• On the forbidden induced subgraph probe and sandwich problems
• The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
• Complexity and algorithms for reasoning about time
• Graph Sandwich Problems

This page was built for publication: A general method for forbidden induced subgraph sandwich problem NP-completeness