{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T00:52:59Z","timestamp":1725583979011},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642387555"},{"type":"electronic","value":"9783642387562"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38756-2_20","type":"book-chapter","created":{"date-parts":[[2013,5,21]],"date-time":"2013-05-21T00:43:48Z","timestamp":1369097028000},"page":"187-197","source":"Crossref","is-referenced-by-count":0,"title":["On (k,\u2113)-Graph Sandwich Problems"],"prefix":"10.1007","author":[{"given":"Fernanda","family":"Couto","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lu\u00e9rbio","family":"Faria","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sulamita","family":"Klein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F\u00e1bio","family":"Protti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Loana T.","family":"Nogueira","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1-3","key":"20_CR1","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0012-365X(94)00296-U","volume":"152","author":"A. Brandstadt","year":"1996","unstructured":"Brandstadt, A.: Partitions of graphs into one or two independent sets and cliques. Discrete Mathematics\u00a0152(1-3), 47\u201354 (1996)","journal-title":"Discrete Mathematics"},{"key":"20_CR2","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/S0012-365X(98)00014-4","volume":"186","author":"A. Brandstadt","year":"2005","unstructured":"Brandstadt, A.: Corrigendum. Discrete Mathematics\u00a0186, 295 (2005)","journal-title":"Discrete Mathematics"},{"issue":"1-3","key":"20_CR3","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0166-218X(98)00116-4","volume":"89","author":"A. Brandstadt","year":"1998","unstructured":"Brandstadt, A., Le, V.B., Szymczak, T.: The complexity of some problems related to graph 3-colorability. Discrete Applied Mathematics\u00a089(1-3), 59\u201373 (1998)","journal-title":"Discrete Applied Mathematics"},{"key":"20_CR4","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.dam.2004.02.008","volume":"143","author":"S. Dantas","year":"2004","unstructured":"Dantas, S., de Figueiredo, C.M., Faria, L.: On decision and optimization (k,l)-graph sandwich problems. Discrete Applied Mathematics\u00a0143, 155\u2013165 (2004)","journal-title":"Discrete Applied Mathematics"},{"issue":"11","key":"20_CR5","doi-asserted-by":"publisher","first-page":"3664","DOI":"10.1016\/j.disc.2008.01.014","volume":"309","author":"S. Dantas","year":"2009","unstructured":"Dantas, S., Klein, S., de Mello, C.P., Morgana, A.: The graph sandwich problem for P4-sparse graphs. Discrete Mathematics\u00a0309(11), 3664\u20133673 (2009)","journal-title":"Discrete Mathematics"},{"doi-asserted-by":"crossref","unstructured":"Dantas, S., Teixeira, R.B., Figueiredo, C.M.H.: The polynomial dichotomy for three nonempty part sandwich problems. Discrete Applied Mathematics, 1286\u20131304 (2010)","key":"20_CR6","DOI":"10.1016\/j.dam.2009.12.002"},{"key":"20_CR7","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/BF03192551","volume":"14","author":"M. Dourado","year":"2008","unstructured":"Dourado, M., Petito, P., Teixeira, R.B., Figueiredo, C.M.H.: Helly property, clique graphs, complementary graph classes, and sandwich problems. Journal Brazilian Computer Society\u00a014, 45\u201352 (2008)","journal-title":"Journal Brazilian Computer Society"},{"unstructured":"Farber, M.: Applications of Linear Programming Duality to Problems Involving Independence and Domination, Ph.d. thesis, Simon Fraser University, Canada (1981)","key":"20_CR8"},{"key":"20_CR9","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1137\/S0895480100384055","volume":"16","author":"T. Feder","year":"2003","unstructured":"Feder, T., Hell, P., Klein, S., Motwani, R.: List partitions. SIAM Journal Discrete Mathematics\u00a016, 449\u2013478 (2003)","journal-title":"SIAM Journal Discrete Mathematics"},{"key":"20_CR10","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/j.tcs.2005.09.030","volume":"349","author":"T. Feder","year":"2005","unstructured":"Feder, T., Hell, P., Klein, S., Nogueira, L.T., Protti, F.: List matrix partitions of chordal graphs. Theoretical Computer Science\u00a0349, 52\u201366 (2005)","journal-title":"Theoretical Computer Science"},{"key":"20_CR11","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.tcs.2007.04.007","volume":"381","author":"C.M.F. Figueiredo","year":"2007","unstructured":"Figueiredo, C.M.F., Faria, L., Klein, S., Sritharan, R.: On the complexity ofthe sandwich problems for strongly chordal graphs and chordal bipartite graphs. Theoretical Computer Science\u00a0381, 57\u201367 (2007)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"20_CR12","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1006\/jagm.1995.1047","volume":"19","author":"M.C. Golumbic","year":"1995","unstructured":"Golumbic, M.C., Kaplan, H., Shamir, R.: Graph sandwich problems. Journal of Algorithms\u00a019(3), 449\u2013473 (1995)","journal-title":"Journal of Algorithms"},{"key":"20_CR13","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0166-218X(03)00371-8","volume":"141","author":"P. Hell","year":"2004","unstructured":"Hell, P., Klein, S., Nogueira, L.T., Protti, F.: Partitioning chordal graphs into independent sets and cliques. Discrete Applied Mathematics\u00a0141, 185\u2013194 (2004)","journal-title":"Discrete Applied Mathematics"},{"key":"20_CR14","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s10479-005-2452-3","volume":"138","author":"P. Hell","year":"2005","unstructured":"Hell, P., Klein, S., Nogueira, L.T., Protti, F.: Packing r-cliques in weighted chordal graphs. Annals of OR\u00a0138, 179\u2013187 (2005)","journal-title":"Annals of OR"},{"issue":"2","key":"20_CR15","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"G. Lueker","year":"1976","unstructured":"Lueker, G., Rose, D., Tarjan, R.E.: Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing\u00a05(2), 266\u2013283 (1976)","journal-title":"SIAM Journal on Computing"},{"unstructured":"Nogueira, L.T.: Grafos split e grafos split generalizados, M.sc. thesis, COPPE\/UFRJ, Rio de Janeiro, RJ, Brasil (1999)","key":"20_CR16"},{"key":"20_CR17","doi-asserted-by":"publisher","first-page":"2581","DOI":"10.1016\/j.disc.2007.06.004","volume":"308","author":"R. Sritharan","year":"2008","unstructured":"Sritharan, R.: Chordal bipartite completion of colored graphs. Discrete Mathematics\u00a0308, 2581\u20132588 (2008)","journal-title":"Discrete Mathematics"},{"key":"20_CR18","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"R.E. Tarjan","year":"1984","unstructured":"Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing\u00a013, 566\u2013579 (1984)","journal-title":"SIAM Journal on Computing"},{"key":"20_CR19","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/0206036","volume":"6","author":"S. Tsukiyama","year":"1977","unstructured":"Tsukiyama, S., Ide, M., Arujoshi, H., Ozaki, H.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput.\u00a06, 505\u2013517 (1977)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics and Algorithmic Aspects in Information and Management"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38756-2_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T03:19:31Z","timestamp":1557717571000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38756-2_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642387555","9783642387562"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38756-2_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}