The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem

DOI10.1016/j.dam.2013.09.004zbMath1306.05160OpenAlexW2066862302MaRDI QIDQ2255038

Rafael B. Teixeira, Simone Dantas, Frédéric Maffray, Celina M. Herrera de Figueiredo

Publication date: 6 February 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.09.004

zbMATH Keywords

perfect graphsforbidden subgraphgraph sandwich problem

Mathematics Subject Classification ID

Perfect graphs (05C17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

A general method for forbidden induced subgraph sandwich problem NP-completeness ⋮ The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy ⋮ Some completion problems for graphs without chordless cycles of prescribed lengths ⋮ Sandwiches missing two ingredients of order four

Cites Work

• Unnamed Item
• Unnamed Item
• The external constraint 4 nonempty part sandwich problem
• On the forbidden induced subgraph sandwich problem
• The chain graph sandwich problem
• The pair completion algorithm for the homogeneous set sandwich problem
• The strong perfect graph theorem
• On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
• Paw-free graphs
• Star-cutsets and perfect graphs
• An algorithm for finding clique cut-sets
• Complexity and algorithms for graph and hypergraph sandwich problems
• On the complexity of DNA physical mapping
• The graph sandwich problem for 1-join composition is NP-complete
• Can transitive orientation make sandwich problems easier?
• Decomposing Berge graphs and detecting balanced skew partitions
• Skew partitions in perfect graphs
• The sandwich problem for cutsets: clique cutset, \(k\)-star cutset
• A Parameterized Algorithm for Chordal Sandwich
• Complexity and algorithms for reasoning about time
• Graph Sandwich Problems
• Fast Skew Partition Recognition
• The complexity of satisfiability problems
• Berge trigraphs
• The polynomial dichotomy for three nonempty part sandwich problems