{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T06:17:16Z","timestamp":1725862636529},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662531730"},{"type":"electronic","value":"9783662531747"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53174-7_22","type":"book-chapter","created":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T14:50:06Z","timestamp":1470322206000},"page":"312-324","source":"Crossref","is-referenced-by-count":0,"title":["On the Complexity of Probe and Sandwich Problems for Generalized Threshold Graphs"],"prefix":"10.1007","author":[{"given":"Fernanda","family":"Couto","sequence":"first","affiliation":[]},{"given":"Luerbio","family":"Faria","sequence":"additional","affiliation":[]},{"given":"Sylvain","family":"Gravier","sequence":"additional","affiliation":[]},{"given":"Sulamita","family":"Klein","sequence":"additional","affiliation":[]},{"given":"Vinicius F.","family":"dos Santos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,8,5]]},"reference":[{"key":"22_CR1","unstructured":"Zhang, P.: Probe interval graph and its application to physical mapping of DNA. Manuscript (1994)"},{"key":"22_CR2","first-page":"309","volume":"10","author":"P Zhang","year":"1994","unstructured":"Zhang, P., Schon, E.A., Fisher, S.G., Cayanis, E., Weiss, J., Kistler, S., Bourne, P.E.: An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA. CABIOS 10, 309\u2013317 (1994)","journal-title":"CABIOS"},{"key":"22_CR3","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1006\/geno.1998.5631","volume":"55","author":"P Zhang","year":"1999","unstructured":"Zhang, P., Ye, X., Liao, L., Russo, J., Fisher, S.G.: Integrated mapping package - a physical mapping software tool kit. Genomics 55, 78\u201387 (1999)","journal-title":"Genomics"},{"key":"22_CR4","unstructured":"Chandler, D.B., Chang, M.-S., Kloks, T., Liu, J., Peng, S.-L.: Probe Graph Classes. Online Manuscript (2012)"},{"issue":"3","key":"22_CR5","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1006\/jagm.1995.1047","volume":"19","author":"MC Golumbic","year":"1995","unstructured":"Golumbic, M.C., Kaplan, H., Shamir, R.: Graph sandwich problems. J. Algorithm 19(3), 449\u2013473 (1995)","journal-title":"J. Algorithm"},{"key":"22_CR6","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/j.tcs.2007.04.007","volume":"381","author":"CMF Figueiredo","year":"2007","unstructured":"Figueiredo, C.M.F., Faria, L., Klein, S., Sritharan, R.: On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs. Theor. Comput. Sci. 381, 57\u201367 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"22_CR7","doi-asserted-by":"crossref","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 Math. 308, 2581\u20132588 (2008)","journal-title":"Discrete Math."},{"issue":"3","key":"22_CR8","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"DG Corneil","year":"1981","unstructured":"Corneil, D.G., Lerchs, H., Burlingham, L.S.: Complement reducible graphs. Discrete App. Math. 3(3), 163\u2013174 (1981)","journal-title":"Discrete App. Math."},{"issue":"4","key":"22_CR9","doi-asserted-by":"crossref","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"DG Corneil","year":"1985","unstructured":"Corneil, D.G., Perl, Y., Stewart, L.K.: A linear recognition algorithm for cographs. SIAM J. Comput. 14(4), 926\u2013934 (1985)","journal-title":"SIAM J. Comput."},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"Bretscher, A., Corneil, D.G., Habib, M., Paul, C.: A simple linear time lexbfs cograph recognition algorithm. In: 29th WG Workshop, pp. 119\u2013130 (2003)","DOI":"10.1007\/978-3-540-39890-5_11"},{"issue":"2","key":"22_CR11","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/j.dam.2004.01.011","volume":"145","author":"M Habib","year":"2005","unstructured":"Habib, M., Paul, C.: A simple linear time algorithm for cograph recognition. Discrete Appl. Math. 145(2), 183\u2013197 (2005)","journal-title":"Discrete Appl. Math."},{"key":"22_CR12","doi-asserted-by":"crossref","unstructured":"Chv\u00e1tal, V., Hammer, P.L.: Aggregation of inequalities in integer programming. In: Korte, B.H., Hammer, P.L., Johnson, E.L., Nemhauser, G.L. (eds.) Studies in Integer Programming, vol. 1, Annals of Discrete Mathematics, pp. 145\u2013162. Elsevier (1977)","DOI":"10.1016\/S0167-5060(08)70731-3"},{"issue":"1\u20133","key":"22_CR13","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0012-365X(94)00296-U","volume":"152","author":"A Brandst\u00e4dt","year":"1996","unstructured":"Brandst\u00e4dt, A.: Partitions of graphs into one or two independent sets and cliques. Discrete Math. 152(1\u20133), 47\u201354 (1996)","journal-title":"Discrete Math."},{"key":"22_CR14","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/S0012-365X(98)00014-4","volume":"186","author":"A Brandst\u00e4dt","year":"2005","unstructured":"Brandst\u00e4dt, A.: Corrigendum. Discrete Math. 186, 295 (2005)","journal-title":"Discrete Math."},{"issue":"1\u20133","key":"22_CR15","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/S0166-218X(98)00116-4","volume":"89","author":"A Brandst\u00e4dt","year":"1998","unstructured":"Brandst\u00e4dt, A., Le, V.B., Szymczak, T.: The complexity of some problems related to graph 3-colorability. Discrete Appl. Math. 89(1\u20133), 59\u201373 (1998)","journal-title":"Discrete Appl. Math."},{"key":"22_CR16","doi-asserted-by":"crossref","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 Appl. Math. 143, 155\u2013165 (2004)","journal-title":"Discrete Appl. Math."},{"key":"22_CR17","first-page":"277","volume":"22","author":"R Bravo","year":"2005","unstructured":"Bravo, R., Klein, S., Nogueira, L.: Characterizing $$(k,\\ell )$$ -partitionable cographs. ENDM 22, 277\u2013280 (2005)","journal-title":"ENDM"},{"key":"22_CR18","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/j.endm.2015.07.023","volume":"50","author":"F Couto","year":"2015","unstructured":"Couto, F., Faria, L., Gravier, S., Klein, S., dos Santos, V.F.: Structural characterization, decomposition for cographs- $$(2,1)$$ , $$(1,2)$$ : a natural generalization of threshold graphs. Electron. Notes Discrete Math. 50, 133\u2013138 (2015)","journal-title":"Electron. Notes Discrete Math."},{"key":"22_CR19","doi-asserted-by":"crossref","unstructured":"de Ridder, H.N.: On probe classes of graphs. Ph.D. thesis, Rostock (2007)","DOI":"10.1016\/j.endm.2006.08.037"},{"key":"22_CR20","unstructured":"Chandler, D.B., Chang, M.-S., Kloks, T., Peng, S.-L.: Probe Graphs. Online Manuscript (2009)"},{"key":"22_CR21","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53174-7_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,12]],"date-time":"2019-09-12T04:53:29Z","timestamp":1568264009000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53174-7_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662531730","9783662531747"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53174-7_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}