{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:18:42Z","timestamp":1725535122991},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642028816"},{"type":"electronic","value":"9783642028823"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-02882-3_40","type":"book-chapter","created":{"date-parts":[[2009,7,10]],"date-time":"2009-07-10T10:49:21Z","timestamp":1247222961000},"page":"398-407","source":"Crossref","is-referenced-by-count":0,"title":["Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone"],"prefix":"10.1007","author":[{"given":"Pinar","family":"Heggernes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Federico","family":"Mancini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charis","family":"Papadopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Sritharan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"40_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Shapira, A.: Every monotone graph property is testable. In: STOC 2005, pp. 128\u2013137 (2005)","DOI":"10.1145\/1060590.1060611"},{"key":"40_CR2","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1023\/A:1022806215452","volume":"46","author":"M. Bakonyi","year":"1997","unstructured":"Bakonyi, M., Bono, A.: Several results on chordal bipartite graphs. Czechoslovak Math. J.\u00a046, 577\u2013583 (1997)","journal-title":"Czechoslovak Math. J."},{"key":"40_CR3","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0166-218X(01)00175-5","volume":"116","author":"J. Balogh","year":"2002","unstructured":"Balogh, J., Bolob\u00e1s, B., Weinreich, D.: Measures on monotone properties of graphs. Disc. Appl. Math.\u00a0116, 17\u201336 (2002)","journal-title":"Disc. Appl. Math."},{"key":"40_CR4","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/S0166-218X(99)00146-8","volume":"99","author":"P. Burzyn","year":"2000","unstructured":"Burzyn, P., Bonomo, F., Duran, G.: NP-completeness results for edge modification problems. Discrete Applied Math.\u00a099, 367\u2013400 (2000)","journal-title":"Discrete Applied Math."},{"key":"40_CR5","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/j.disc.2005.12.017","volume":"306","author":"H.L. Bodlaender","year":"2006","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Safe separators for treewidth. Discrete Math.\u00a0306, 337\u2013350 (2006)","journal-title":"Discrete Math."},{"key":"40_CR6","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1137\/S0097539799359683","volume":"31","author":"V. Bouchitt\u00e9","year":"2001","unstructured":"Bouchitt\u00e9, V., Todinca, I.: Treewidth and minimum fill-in: Grouping the minimal separators. SIAM J. Comput.\u00a031, 212\u2013232 (2001)","journal-title":"SIAM J. Comput."},{"key":"40_CR7","unstructured":"Dahlhaus, E.: Chordale graphen im besonderen hinblick auf parallele algorithmen, Habilitation thesis, Universit\u00e4t Bonn (1991)"},{"key":"40_CR8","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0012-365X(83)90154-1","volume":"43","author":"M. Farber","year":"1983","unstructured":"Farber, M.: Characterizations on strongly chordal graphs. Discrete Mathematics\u00a043, 173\u2013189 (1983)","journal-title":"Discrete Mathematics"},{"key":"40_CR9","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.tcs.2007.04.007","volume":"381","author":"C.M.H. Figueiredo de","year":"2007","unstructured":"de Figueiredo, C.M.H., Faria, L., Klein, S., Sritharan, R.: On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs. Theoretical Computer Science\u00a0381, 57\u201367 (2007)","journal-title":"Theoretical Computer Science"},{"key":"40_CR10","doi-asserted-by":"publisher","first-page":"1058","DOI":"10.1137\/050643350","volume":"38","author":"F.V. Fomin","year":"2008","unstructured":"Fomin, F.V., Kratsch, D., Todinca, I., Villanger, Y.: Exact algorithms for treewidth and minimum fill-in. SIAM J. Computing\u00a038, 1058\u20131079 (2008)","journal-title":"SIAM J. Computing"},{"issue":"1","key":"40_CR11","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1089\/cmb.1995.2.139","volume":"2","author":"P.W. Goldberg","year":"1995","unstructured":"Goldberg, P.W., Golumbic, M.C., Kaplan, H., Shamir, R.: Four strikes against physical mapping of DNA. J. Comput. Bio.\u00a02(1), 139\u2013152 (1995)","journal-title":"J. Comput. Bio."},{"key":"40_CR12","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edn. Annals of Discrete Mathematics, vol.\u00a057. Elsevier, Amsterdam (2004)","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"40_CR13","doi-asserted-by":"crossref","unstructured":"Heggernes, P., Mancini, F.: Minimal split completions. Discrete Applied Mathematics (in print); also In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol.\u00a03887, pp. 592\u2013604. Springer, Heidelberg (2006)","DOI":"10.1007\/11682462_55"},{"key":"40_CR14","doi-asserted-by":"crossref","unstructured":"Heggernes, P., Suchan, K., Todinca, I., Villanger, Y.: Characterizing minimal interval completions: Towards better understanding of profile and pathwidth. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 236\u2013247. Springer, Heidelberg (2007)","DOI":"10.1007\/978-3-540-70918-3_21"},{"key":"40_CR15","doi-asserted-by":"crossref","unstructured":"Heggernes, P., Papadopoulos, C.: Single-Edge Monotonic Sequences of Graphs and Linear-Time Algorithms for Minimal Completions and Deletions. Theoretical Computer Science 410, 1\u201315 (2009); also In: Lin, G. (ed.) COCOON 2007. LNCS, vol.\u00a04598, pp. 406\u2013416. Springer, Heidelberg (2007)","DOI":"10.1016\/j.tcs.2008.07.020"},{"key":"40_CR16","doi-asserted-by":"publisher","first-page":"1906","DOI":"10.1137\/S0097539796303044","volume":"28","author":"H. Kaplan","year":"1999","unstructured":"Kaplan, H., Shamir, R., Tarjan, R.E.: Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM J.\u00a0Comput.\u00a028, 1906\u20131922 (1999)","journal-title":"SIAM J.\u00a0Comput."},{"key":"40_CR17","doi-asserted-by":"crossref","unstructured":"Kijima, S., Kiyomi, M., Okamoto, Y., Uno, T.: On listing, sampling, and counting the chordal graphs with edge constraints. In: Hu, X., Wang, J. (eds.) COCOON 2008. LNCS, vol.\u00a05092, pp. 458\u2013467. Springer, Heidelberg (2008)","DOI":"10.1007\/978-3-540-69733-6_45"},{"key":"40_CR18","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Mancini, F., Papadopoulos, C.: Characterizing and Computing Minimal Cograph Completions. In: Preparata, F.P., Wu, X., Yin, J. (eds.) FAW 2008. LNCS, vol.\u00a05059, pp. 147\u2013158. Springer, Heidelberg (2008)","DOI":"10.1007\/978-3-540-69311-6_17"},{"key":"40_CR19","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/S0166-218X(00)00391-7","volume":"113","author":"A. Natanzon","year":"2001","unstructured":"Natanzon, A., Shamir, R., Sharan, R.: Complexity classification of some edge modification problems. Disc. Appl. Math.\u00a0113, 109\u2013128 (2001)","journal-title":"Disc. Appl. Math."},{"key":"40_CR20","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1137\/0216062","volume":"16","author":"R. Paige","year":"1987","unstructured":"Paige, R., Tarjan, R.E.: Three partition refinement algorithms. SIAM J.\u00a0Comput.\u00a016, 973\u2013989 (1987)","journal-title":"SIAM J.\u00a0Comput."},{"key":"40_CR21","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1016\/0022-247X(70)90282-9","volume":"32","author":"D. Rose","year":"1970","unstructured":"Rose, D.: Triangulated graphs and the elimination process. J. Math. Anal. Appl.\u00a032, 597\u2013609 (1970)","journal-title":"J. Math. Anal. Appl."},{"key":"40_CR22","doi-asserted-by":"crossref","unstructured":"Rose, D.J.: A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. In: Read, R.C. (ed.) Graph Theory and Computing, pp. 183\u2013217. Academic Press, New York (1972)","DOI":"10.1016\/B978-1-4832-3187-7.50018-0"},{"key":"40_CR23","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D. Rose","year":"1976","unstructured":"Rose, D., Tarjan, R.E., Lueker, G.: Algorithmic aspects of vertex elimination on graphs. SIAM J.\u00a0Comput.\u00a05, 266\u2013283 (1976)","journal-title":"SIAM J.\u00a0Comput."},{"key":"40_CR24","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":"40_CR25","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0020-0190(93)90209-R","volume":"45","author":"J.P. Spinrad","year":"1993","unstructured":"Spinrad, J.P.: Doubly lexical ordering of dense 0-1 matrices. Information Processing Letters\u00a045, 229\u2013235 (1993)","journal-title":"Information Processing Letters"},{"key":"40_CR26","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"M. Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Alg. Disc. Meth.\u00a02, 77\u201379 (1981)","journal-title":"SIAM J. Alg. Disc. Meth."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02882-3_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T10:44:49Z","timestamp":1558435489000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02882-3_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642028816","9783642028823"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02882-3_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}