The homogeneous set sandwich problem

DOI10.1016/S0020-0190(98)00076-3MaRDI QIDQ293307zbMATHFDO

Authors Márcia R. Cerioli, Hazel Everett, Sulamita Klein, Celina M. H. 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

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

Recommendations

• Note on the homogeneous set sandwich problem
• Algorithms for the homogeneous set sandwich problem
• A note on finding all homogeneous set sandwiches
• Complexity issues for the sandwich homogeneous set problem
• An efficient algorithm for solving the homogeneous set sandwich problem
• The pair completion algorithm for the homogeneous set sandwich problem
• The sandwich problem for decompositions and almost monotone properties
• The chain graph sandwich problem
• Bounded degree interval sandwich problems
• Sandwich classification theorem

Cites work

• scientific article; zbMATH DE number 1003286 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A semi-strong perfect graph theorem
• Comparability graphs and a new matroid
• Compositions for perfect graphs
• Computing the Minimum Fill-In is NP-Complete
• Graph Sandwich Problems
• Incremental modular decomposition
• Normal hypergraphs and the perfect graph conjecture
• Recognizing bull-free perfect graphs
• Total chromatic number of unichord-free graphs
• \(P_ 4\)-trees and substitution decomposition

Cited in

(27)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q293307)