The chain graph sandwich problem

DOI10.1007/S10479-010-0792-0zbMATH Open1250.05106OpenAlexW2069690101MaRDI QIDQ646705FDOQ646705

Martin Charles Golumbic, Frédéric Maffray, Simone Dantas, Celina M. H. de Figueiredo, Sulamita Klein

Publication date: 17 November 2011

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-010-0792-0

Recommendations

• Graph Sandwich Problems
• Algorithms and complexity of sandwich problems in graphs (extended abstract)
• On \((k,\ell )\)-graph sandwich problems
• Complexity and algorithms for graph and hypergraph sandwich problems
• On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
• scientific article; zbMATH DE number 1953085
• Partitions and well-coveredness: the graph sandwich problem
• On the forbidden induced subgraph sandwich problem
• The graph sandwich problem for \(P_4\)-sparse graphs
• The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem

zbMATH Keywords

NP-completechain graph sandwich problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Graph Sandwich Problems
• Threshold graphs and related topics
• Node-Deletion Problems on Bipartite Graphs
• Difference graphs
• Chordal bipartite completion of colored graphs
• On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
• On the complexity of bicoloring clique hypergraphs of graphs
• The graph sandwich problem for \(P_4\)-sparse graphs
• Landmarks in Algorithmic Graph Theory: A Personal Retrospective
• The polynomial dichotomy for three nonempty part sandwich problems

Cited In (9)

• Can transitive orientation make sandwich problems easier?
• 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 homogeneous set sandwich problem
• Some completion problems for graphs without chordless cycles of prescribed lengths
• Sandwiches missing two ingredients of order four
• A vertex ordering characterization of simple-triangle graphs
• Recognizing simple-triangle graphs by restricted 2-chain subgraph cover
• Graph Sandwich Problems

This page was built for publication: The chain graph sandwich problem

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