Back to Search
Start Over
On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
- Source :
-
Theoretical Computer Science . Aug2007, Vol. 381 Issue 1-3, p57-67. 11p. - Publication Year :
- 2007
-
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. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 381
- Issue :
- 1-3
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 26041508
- Full Text :
- https://doi.org/10.1016/j.tcs.2007.04.007