{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:56:39Z","timestamp":1725562599055},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540220671"},{"type":"electronic","value":"9783540248385"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24838-5_18","type":"book-chapter","created":{"date-parts":[[2010,8,8]],"date-time":"2010-08-08T21:34:14Z","timestamp":1281303254000},"page":"243-252","source":"Crossref","is-referenced-by-count":0,"title":["Faster Deterministic and Randomized Algorithms on the Homogeneous Set Sandwich Problem"],"prefix":"10.1007","author":[{"given":"Celina M. H.","family":"de Figueiredo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guilherme D.","family":"da Fonseca","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vin\u00edcius G. P.","family":"de S\u00e1","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeremy","family":"Spinrad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"18_CR1","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0020-0190(98)00076-3","volume":"67","author":"M.R. Cerioli","year":"1998","unstructured":"Cerioli, M.R., Everett, H., de Figueiredo, C.M.H., Klein, S.: The homogeneous set sandwich problem. Information Processing Letters\u00a067, 31\u201335 (1998)","journal-title":"Information Processing Letters"},{"key":"18_CR2","unstructured":"de Figueiredo, C.M.H., de S\u00e1, V.G.P.: A new upper bound for the homogeneous set sandwich problem. Technical report, COPPE\/Sistemas, Universidade Federal do Rio de Janeiro (2004)"},{"key":"18_CR3","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/S0166-218X(01)00246-3","volume":"121","author":"C.M.H. Figueiredo de","year":"2002","unstructured":"de Figueiredo, C.M.H., Klein, S., Vu\u0161kovi\u0107, K.: The graph sandwich problem for 1-join composition is NP-complete. Discrete Appl. Math.\u00a0121, 73\u201382 (2002)","journal-title":"Discrete Appl. Math."},{"key":"18_CR4","unstructured":"de S\u00e1, V.G.P.: The sandwich problem for homogeneous sets in graphs. Master\u2019s thesis, COPPE \/ Universidade Federal do Rio de Janeiro (May 2003) (in Portuguese)"},{"key":"18_CR5","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0024-3795(97)10075-1","volume":"277","author":"M.C. Golumbic","year":"1998","unstructured":"Golumbic, M.C.: Matrix sandwich problems. Linear Algebra Appl.\u00a0277, 239\u2013251 (1998)","journal-title":"Linear Algebra Appl."},{"key":"18_CR6","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, 449\u2013473 (1995)","journal-title":"Journal of Algorithms"},{"key":"18_CR7","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s003730050028","volume":"14","author":"M.C. Golumbic","year":"1998","unstructured":"Golumbic, M.C., Wassermann, A.: Complexity and algorithms for graph and hypergraph sandwich problems. Graphs Combin.\u00a014, 223\u2013239 (1998)","journal-title":"Graphs Combin."},{"key":"18_CR8","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1137\/S0097539793258143","volume":"25","author":"H. Kaplan","year":"1996","unstructured":"Kaplan, H., Shamir, R.: Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques. SIAM J. Comput.\u00a025, 540\u2013561 (1996)","journal-title":"SIAM J. Comput."},{"key":"18_CR9","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/PL00009277","volume":"24","author":"H. Kaplan","year":"1999","unstructured":"Kaplan, H., Shamir, R.: Bounded degree interval sandwich problems. Algorithmica\u00a024, 96\u2013104 (1999)","journal-title":"Algorithmica"},{"key":"18_CR10","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0012-365X(72)90006-4","volume":"2","author":"L. Lov\u00e1sz","year":"1972","unstructured":"Lov\u00e1sz, L.: Normal hypergraphs and the perfect graph conjecture. Discrete Math.\u00a02, 253\u2013267 (1972)","journal-title":"Discrete Math."},{"key":"18_CR11","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"R.M. McConnell","year":"1999","unstructured":"McConnell, R.M., Spinrad, J.: Modular decomposition and transitive orientations. Discrete Math.\u00a0201, 189\u2013241 (1999)","journal-title":"Discrete Math."},{"key":"18_CR12","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0020-0190(00)00145-9","volume":"77","author":"S. Tang","year":"2001","unstructured":"Tang, S., Yeh, F., Wang, Y.: An efficient algorithm for solving the homogeneous set sandwich problem. Information Processing Letters\u00a077, 17\u201322 (2001)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Experimental and Efficient Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24838-5_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,17]],"date-time":"2019-03-17T23:45:04Z","timestamp":1552866304000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24838-5_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540220671","9783540248385"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24838-5_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}