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
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
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 (12)
- 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
- Recognizing simple-triangle graphs by restricted 2-chain subgraph cover
- 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)
