Complexity and algorithms for graph and hypergraph sandwich problems
From MaRDI portal
Publication:1268114
DOI10.1007/s003730050028zbMath0906.68109MaRDI QIDQ1268114
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
68Q25: Analysis of algorithms and problem complexity
05C65: Hypergraphs
68R10: Graph theory (including graph drawing) in computer science
05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Unnamed Item, The external constraint 4 nonempty part sandwich problem, The pair completion algorithm for the homogeneous set sandwich problem, On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs, The graph sandwich problem for \(P_4\)-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, The sandwich problem for cutsets: clique cutset, \(k\)-star cutset, Tree Projections: Game Characterization and Computational Aspects