Complexity and algorithms for graph and hypergraph sandwich problems

DOI10.1007/S003730050028MaRDI QIDQ1268114zbMATH OpenOpenAlexFDO

Authors Martin Charles Golumbic, Amir Wassermann

Publication date 14 October 1998

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s003730050028

zbMATH Keywords

hypergraph sandwich problem

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Hypergraphs (05C65)

Recommendations

• Algorithms and complexity of sandwich problems in graphs (extended abstract)
• scientific article; zbMATH DE number 1953085
• On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
• On (k, )-graph sandwich problems
• Complexity issues for the sandwich homogeneous set problem
• The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
• Total exchange algorithms on 'sandwich graphs'
• Graph Sandwich Problems
• On the complexity of probe and sandwich problems for generalized threshold graphs
• On decision and optimization (\(k\),\(l\))-graph sandwich problems

Cited in

(19)

• Can transitive orientation make sandwich problems easier?
• scientific article; zbMATH DE number 2230229 (Why is no real title available?)
• The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
• The graph sandwich problem for P₄-sparse graphs
• On probe interval graphs
• Matrix sandwich problems
• The graph sandwich problem for 1-join composition is NP-complete
• On decision and optimization (\(k\),\(l\))-graph sandwich problems
• Complexity issues for the sandwich homogeneous set problem
• The external constraint 4 nonempty part sandwich problem
• The chain graph sandwich problem
• The pair completion algorithm for the homogeneous set sandwich problem
• The sandwich problem for cutsets: clique cutset, \(k\)-star cutset
• scientific article; zbMATH DE number 4117862 (Why is no real title available?)
• On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
• Tree projections: Game characterization and computational aspects
• Graph Sandwich Problems
• Tree-Related Widths of Graphs and Hypergraphs
• scientific article; zbMATH DE number 5999585 (Why is no real title available?)

This page was built for publication: Complexity and algorithms for graph and hypergraph sandwich problems

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