The homogeneous set sandwich problem

DOI10.1016/S0020-0190(98)00076-3zbMath1339.05382MaRDI QIDQ293307

Márcia R. Cerioli, Hazel Everett, Sulamita Klein, Celina M. Herrera de Figueiredo

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019098000763?np=y

zbMATH Keywords

design of algorithmsperfect graphssandwich problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (22)

The graph sandwich problem for 1-join composition is NP-complete ⋮ Note on the homogeneous set sandwich problem ⋮ Can transitive orientation make sandwich problems easier? ⋮ On decision and optimization (\(k\),\(l\))-graph sandwich problems ⋮ The pair completion algorithm for the homogeneous set sandwich problem ⋮ On the forbidden induced subgraph sandwich problem ⋮ The polynomial dichotomy for three nonempty part sandwich problems ⋮ The polynomial dichotomy for three nonempty part sandwich problems ⋮ Complexity issues for the sandwich homogeneous set problem ⋮ The external constraint 4 nonempty part sandwich problem ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory ⋮ Competitive graph searches ⋮ The sandwich problem for cutsets: clique cutset, \(k\)-star cutset ⋮ On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs ⋮ Sandwiches missing two ingredients of order four ⋮ The sandwich problem for decompositions and almost monotone properties ⋮ A note on finding all homogeneous set sandwiches ⋮ The graph sandwich problem for \(P_4\)-sparse graphs ⋮ Unnamed Item ⋮ Skew partition sandwich problem is NP-complete ⋮ The P4-sparse Graph Sandwich Problem ⋮ An efficient algorithm for solving the homogeneous set sandwich problem

Cites Work

• Unnamed Item
• Unnamed Item
• Total chromatic number of unichord-free graphs
• A semi-strong perfect graph theorem
• \(P_ 4\)-trees and substitution decomposition
• Comparability graphs and a new matroid
• Recognizing bull-free perfect graphs
• Compositions for perfect graphs
• Normal hypergraphs and the perfect graph conjecture
• Incremental modular decomposition
• Computing the Minimum Fill-In is NP-Complete
• Graph Sandwich Problems

This page was built for publication: The homogeneous set sandwich problem