The chain graph sandwich problem

DOI10.1007/s10479-010-0792-0zbMath1250.05106OpenAlexW2069690101MaRDI QIDQ646705

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

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

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)

Related Items (5)

Recognizing simple-triangle graphs by restricted 2-chain subgraph cover ⋮ The complexity of forbidden subgraph sandwich problems and the skew partition 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

Cites Work

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

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