{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:40:59Z","timestamp":1740109259965,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2018,1,19]],"date-time":"2018-01-19T00:00:00Z","timestamp":1516320000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,1,19]],"date-time":"2018-01-19T00:00:00Z","timestamp":1516320000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1550991"],"award-info":[{"award-number":["DMS-1550991"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-16-1-0404"],"award-info":[{"award-number":["W911NF-16-1-0404"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["303622\/2011-3"],"award-info":[{"award-number":["303622\/2011-3"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,12]]},"DOI":"10.1007\/s00453-018-0409-6","type":"journal-article","created":{"date-parts":[[2018,1,19]],"date-time":"2018-01-19T19:35:34Z","timestamp":1516390534000},"page":"3618-3645","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Sandwich Problem for Decompositions and Almost Monotone Properties"],"prefix":"10.1007","volume":"80","author":[{"given":"Maria","family":"Chudnovsky","sequence":"first","affiliation":[]},{"given":"Celina M. H.","family":"de Figueiredo","sequence":"additional","affiliation":[]},{"given":"Sophie","family":"Spirkl","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,1,19]]},"reference":[{"issue":"114","key":"409_CR1","first-page":"114","volume":"10","author":"C Berge","year":"1961","unstructured":"Berge, C.: F\u00e4rbung von Graphen, deren s\u00e4mtliche bzw. deren ungerade Kreise starr sind. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10(114), 114 (1961)","journal-title":"Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe"},{"issue":"3","key":"409_CR2","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1137\/050637091","volume":"21","author":"A Berry","year":"2007","unstructured":"Berry, A., Golumbic, M.C., Lipshteyn, M.: Recognizing chordal probe graphs and cycle-bicolorable graphs. SIAM J. Discrete Math. 21(3), 573\u2013591 (2007)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"409_CR3","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0166-218X(00)00197-9","volume":"105","author":"A Brandst\u00e4dt","year":"2000","unstructured":"Brandst\u00e4dt, A., Dragan, F.F., Szymczak, T.: On stable cutsets in graphs. Discrete Appl. Math. 105(1), 39\u201350 (2000)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"409_CR4","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0020-0190(98)00076-3","volume":"67","author":"MR Cerioli","year":"1998","unstructured":"Cerioli, M.R., Everett, H., de Figueiredo, C.M.H., Klein, S.: The homogeneous set sandwich problem. Inf. Process. Lett. 67(1), 31\u201335 (1998)","journal-title":"Inf. Process. Lett."},{"key":"409_CR5","unstructured":"Chudnovsky, M.: Berge trigraphs and their applications. PhD thesis, Princeton University (2003)"},{"issue":"2","key":"409_CR6","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s00493-005-0012-8","volume":"25","author":"M Chudnovsky","year":"2005","unstructured":"Chudnovsky, M., Cornu\u00e9jols, G., Liu, X., Seymour, P., Vu\u0161kovi\u0107, K.: Recognizing Berge graphs. Combinatorica 25(2), 143\u2013186 (2005)","journal-title":"Combinatorica"},{"issue":"1","key":"409_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/jgt.20165","volume":"53","author":"M Chudnovsky","year":"2006","unstructured":"Chudnovsky, M.: Berge trigraphs. J. Graph Theory 53(1), 1\u201355 (2006)","journal-title":"J. Graph Theory"},{"issue":"1","key":"409_CR8","doi-asserted-by":"publisher","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M Chudnovsky","year":"2006","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164(1), 51\u2013229 (2006)","journal-title":"Ann. Math."},{"issue":"3","key":"409_CR9","doi-asserted-by":"publisher","first-page":"1164","DOI":"10.1137\/060672613","volume":"22","author":"M Chudnovsky","year":"2008","unstructured":"Chudnovsky, M., Kapadia, R.: Detecting a theta or a prism. SIAM J. Discrete Math. 22(3), 1164\u20131186 (2008)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"409_CR10","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/s00493-010-2334-4","volume":"30","author":"M Chudnovsky","year":"2010","unstructured":"Chudnovsky, M., Seymour, P.: The three-in-a-tree problem. Combinatorica 30(4), 387\u2013417 (2010)","journal-title":"Combinatorica"},{"issue":"1","key":"409_CR11","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1002\/jgt.3190080106","volume":"8","author":"V Chv\u00e1tal","year":"1984","unstructured":"Chv\u00e1tal, V.: Recognizing decomposable graphs. J. Graph Theory 8(1), 51\u201353 (1984)","journal-title":"J. Graph Theory"},{"issue":"3","key":"409_CR12","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0095-8956(85)90049-8","volume":"39","author":"V Chv\u00e1tal","year":"1985","unstructured":"Chv\u00e1tal, V.: Star-cutsets and perfect graphs. J. Comb. Theory Ser. B 39(3), 189\u2013199 (1985)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"4","key":"409_CR13","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1002\/jgt.10045","volume":"40","author":"M Conforti","year":"2002","unstructured":"Conforti, M., Cornu\u00e9jols, G., Kapoor, A., Vu\u0161kovi\u0107, K.: Even-hole-free graphs part II: recognition algorithm. J. Graph Theory 40(4), 238\u2013266 (2002)","journal-title":"J. Graph Theory"},{"key":"409_CR14","unstructured":"Couto. F, Faria, L., Gravier, S., Klein, S.: On the forbidden induced subgraph probe and sandwich problems. Discrete Appl. Math. 234, 56\u201366 (2016)"},{"issue":"2","key":"409_CR15","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1137\/0603021","volume":"3","author":"WH Cunningham","year":"1982","unstructured":"Cunningham, W.H.: Decomposition of directed graphs. SIAM J. Algebr. Discrete Methods 3(2), 214\u2013228 (1982)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"issue":"16","key":"409_CR16","doi-asserted-by":"publisher","first-page":"1717","DOI":"10.1016\/j.dam.2010.11.010","volume":"159","author":"S Dantas","year":"2011","unstructured":"Dantas, S., de Figueiredo, C.M.H., da Silva, M.V.G., Teixeira, R.B.: On the forbidden induced subgraph sandwich problem. Discrete Appl. Math. 159(16), 1717\u20131725 (2011)","journal-title":"Discrete Appl. Math."},{"issue":"37","key":"409_CR17","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1006\/jagm.1999.1122","volume":"2","author":"CMH de Figueiredo","year":"2000","unstructured":"de Figueiredo, C.M.H., Klein, S., Kohayakawa, Y., Reed, B.A.: Finding skew partitions efficiently. J. Algorithms 2(37), 505\u2013521 (2000)","journal-title":"J. Algorithms"},{"issue":"1","key":"409_CR18","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/S0166-218X(01)00246-3","volume":"121","author":"CMH de Figueiredo","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. 121(1), 73\u201382 (2002)","journal-title":"Discrete Appl. Math."},{"issue":"1-2","key":"409_CR19","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"G. A. Dirac","year":"1961","unstructured":"Dirac, G.A.: On rigid circuit graphs. In: Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg, vol. 25, no. 1, pp. 71\u201376. Springer, Berlin (1961)","journal-title":"Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg"},{"key":"409_CR20","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/0304-3975(86)90184-2","volume":"43","author":"K Edwards","year":"1986","unstructured":"Edwards, K.: The complexity of colouring problems on dense graphs. Theor. Comput. Sci. 43, 337\u2013343 (1986)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"409_CR21","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0166-218X(95)00090-E","volume":"72","author":"H Everett","year":"1997","unstructured":"Everett, H., Klein, S., Reed, B.: An algorithm for finding homogeneous pairs. Discrete Appl. Math. 72(3), 209\u2013218 (1997)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"409_CR22","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 J. Discrete Math. 16(3), 449\u2013478 (2003)","journal-title":"SIAM J. Discrete Math."},{"issue":"5","key":"409_CR23","doi-asserted-by":"publisher","first-page":"1108","DOI":"10.1145\/174147.169675","volume":"40","author":"MC Golumbic","year":"1993","unstructured":"Golumbic, M.C., Shamir, R.: Complexity and algorithms for reasoning about time: a graph-theoretic approach. J. ACM: JACM 40(5), 1108\u20131133 (1993)","journal-title":"J. ACM: JACM"},{"issue":"3","key":"409_CR24","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1006\/jagm.1995.1047","volume":"19","author":"MC Golumbic","year":"1995","unstructured":"Golumbic, M.C., Kaplan, H.: Graph sandwich problems. J. Algorithms 19(3), 449\u2013473 (1995)","journal-title":"J. Algorithms"},{"issue":"1","key":"409_CR25","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/j.dam.2003.12.009","volume":"143","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C., Lipshteyn, M.: Chordal probe graphs. Discrete Appl. Math. 143(1), 221\u2013237 (2004)","journal-title":"Discrete Appl. Math."},{"key":"409_CR26","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/978-3-540-89550-3_11","volume-title":"Computational Geometry and Graph Theory","author":"William S. Kennedy","year":"2008","unstructured":"Kennedy, W.S., Reed, B.: Fast skew partition recognition. In: Ito, H., Kano, M., Katoh, N., Uno, Y. (eds.) Computational Geometry and Graph Theory, pp. 101\u2013107. Springer, Berlin (2008)"},{"issue":"3","key":"409_CR27","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1137\/S0895480104442522","volume":"19","author":"F Maffray","year":"2005","unstructured":"Maffray, F., Trotignon, N.: Algorithms for perfectly contractile graphs. SIAM J. Discrete Math. 19(3), 553\u2013574 (2005)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"409_CR28","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/S0166-218X(98)00077-8","volume":"88","author":"FR McMorris","year":"1998","unstructured":"McMorris, F.R., Wang, C., Zhang, P.: On probe interval graphs. Discrete Appl. Math. 88(1), 315\u2013324 (1998)","journal-title":"Discrete Appl. Math."},{"issue":"5","key":"409_CR29","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1002\/jgt.3190130502","volume":"13","author":"AM Moshi","year":"1989","unstructured":"Moshi, A.M.: Matching cutsets in graphs. J. Graph Theory 13(5), 527\u2013536 (1989)","journal-title":"J. Graph Theory"},{"issue":"1","key":"409_CR30","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1112\/plms\/s2-30.1.264","volume":"s2-30","author":"F. P. Ramsey","year":"1930","unstructured":"Ramsey, F. P.: On a problem of formal logic. In: Proceedings of the London Mathematical Society, 2nd Series, vol. 30, pp. 264\u2013344 (1930)","journal-title":"Proceedings of the London Mathematical Society"},{"issue":"3","key":"409_CR31","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0166-218X(92)90180-I","volume":"39","author":"J Spinrad","year":"1992","unstructured":"Spinrad, J.: $$P_4$$-trees and substitution decomposition. Discrete Appl. Math. 39(3), 263\u2013291 (1992)","journal-title":"Discrete Appl. Math."},{"issue":"13","key":"409_CR32","doi-asserted-by":"publisher","first-page":"1791","DOI":"10.1016\/j.dam.2006.03.023","volume":"154","author":"RB Teixeira","year":"2006","unstructured":"Teixeira, R.B., de Figueiredo, C.M.H.: The sandwich problem for cutsets: clique cutset, $$k$$-star cutset. Discrete Appl. Math. 154(13), 1791\u20131798 (2006)","journal-title":"Discrete Appl. Math."},{"key":"409_CR33","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.endm.2009.11.003","volume":"35","author":"RB Teixeira","year":"2009","unstructured":"Teixeira, R.B., Dantas, S.: Skew partition sandwich problem is NP-complete. Electron. Notes Discrete Math. 35, 9\u201314 (2009)","journal-title":"Electron. Notes Discrete Math."},{"issue":"2","key":"409_CR34","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1016\/0095-8956(82)90028-4","volume":"32","author":"K Truemper","year":"1982","unstructured":"Truemper, K.: Alpha-balanced graphs and matrices and $$GF(3)$$-representability of matroids. J. Comb. Theory Ser. B 32(2), 112\u2013139 (1982)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"409_CR35","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0020-0190(81)90072-7","volume":"12","author":"SH Whitesides","year":"1981","unstructured":"Whitesides, S.H.: An algorithm for finding clique cut-sets. Inf. Process. Lett. 12(1), 31\u201332 (1981)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"409_CR36","first-page":"309","volume":"10","author":"P Zhang","year":"1994","unstructured":"Zhang, P., Schon, E.A., Fischer, 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. Comput. Appl. Biosci.: CABIOS 10(3), 309\u2013317 (1994)","journal-title":"Comput. Appl. Biosci.: CABIOS"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0409-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0409-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0409-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:31:11Z","timestamp":1589697071000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0409-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,19]]},"references-count":36,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["409"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0409-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,1,19]]},"assertion":[{"value":"21 March 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 January 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 January 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}