| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 436805 | Theoretical Computer Science | 2007 | 11 Pages |
Abstract
Golumbic, Kaplan, and Shamir, in their paper [M.C. Golumbic, H. Kaplan, R. Shamir, Graph sandwich problems, J. Algorithms 19 (1995) 449–473] on graph sandwich problems published in 1995, left the status of sandwich problems for strongly chordal graphs and chordal bipartite graphs open. We prove that the sandwich problem for strongly chordal graphs is NP-complete. We also give some comments on the computational complexity of the sandwich problem for chordal bipartite graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
