The chain graph sandwich problem

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

Authors Simone Dantas, Martin Charles Golumbic, Sulamita Klein, Frédéric Maffray, Celina M. H. 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)

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

Cites Work

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

Cited In (11)

• 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 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
• Graph Sandwich Problems
• A parameterized algorithm for chordal sandwich
• On \((k,\ell )\)-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)