{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:47:32Z","timestamp":1725497252006},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540771180"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77120-3_76","type":"book-chapter","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T11:31:09Z","timestamp":1196940669000},"page":"881-892","source":"Crossref","is-referenced-by-count":4,"title":["Minimum Fill-In and Treewidth of Split+\u2009ke and Split+\u2009kv Graphs"],"prefix":"10.1007","author":[{"given":"Federico","family":"Mancini","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"76_CR1","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/S0166-218X(00)00391-7","volume":"113","author":"R. Shamir","year":"2001","unstructured":"Shamir, R., Natanzon, A., Sharan, R.: Complexity classification of some edge modification problems. Discrete Applied Mathematics\u00a0113(1), 109\u2013128 (2001)","journal-title":"Discrete Applied Mathematics"},{"key":"76_CR2","first-page":"1","volume-title":"Graph Theory and Sparse Matrix Computations","author":"J.R.S. Blair","year":"1993","unstructured":"Blair, J.R.S., Peyton, B.: An introduction to chordal graphs and clique trees. In: Graph Theory and Sparse Matrix Computations, pp. 1\u201329. Springer, Heidelberg (1993)"},{"key":"76_CR3","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"SOFSEM 2005: Theory and Practice of Computer Science","author":"H.L. Bodlaender","year":"2005","unstructured":"Bodlaender, H.L.: Discovering treewidth. In: Vojt\u00e1\u0161, P., Bielikov\u00e1, M., Charron-Bost, B., S\u00fdkora, O. (eds.) SOFSEM 2005. LNCS, vol.\u00a03381, pp. 1\u201316. Springer, Heidelberg (2005)"},{"issue":"4","key":"76_CR4","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"L. Cai","year":"1996","unstructured":"Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett.\u00a058(4), 171\u2013176 (1996)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"76_CR5","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1016\/S0166-218X(02)00242-1","volume":"127","author":"L. Cai","year":"2003","unstructured":"Cai, L.: Parameterized complexity of vertex colouring. Discrete Applied Mathematics\u00a0127(3), 415\u2013429 (2003)","journal-title":"Discrete Applied Mathematics"},{"key":"76_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/BFb0024494","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"E. Dahlhaus","year":"1997","unstructured":"Dahlhaus, E.: Minimal elimination ordering inside a given chordal graph. In: M\u00f6hring, R.H. (ed.) WG 1997. LNCS, vol.\u00a01335, pp. 132\u2013143. Springer, Heidelberg (1997)"},{"key":"76_CR7","doi-asserted-by":"crossref","unstructured":"Dirac, G.A.: On rigid circuit graphs. In: Abhandlungen aus dem Mathematischen Seminar der Universiat Hamburg, vol.\u00a025, pp. 71\u201375 (1961)","DOI":"10.1007\/BF02992776"},{"key":"76_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"76_CR9","unstructured":"Foldes, S., Hammer, P.L.: Split graphs. In: 8th South-Eastern Conference on Combinatorics, Graph Theory and Computing, pp. 311\u2013315 (1977)"},{"key":"76_CR10","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, 1st edn. Academic Press, London (1980)","edition":"1"},{"key":"76_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1007\/978-3-540-28639-4_15","volume-title":"Parameterized and Exact Computation","author":"J. Guo","year":"2004","unstructured":"Guo, J., H\u00fcffner, F., Niedermeier, R.: A structural view on parameterizing problems: Distance from triviality. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol.\u00a03162, pp. 162\u2013173. Springer, Heidelberg (2004)"},{"issue":"3","key":"76_CR12","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/BF02579333","volume":"1","author":"P.L. Hammer","year":"1981","unstructured":"Hammer, P.L., Simeone, B.: The splittance of a graph. Combinatorica\u00a01(3), 275\u2013284 (1981)","journal-title":"Combinatorica"},{"issue":"3","key":"76_CR13","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/j.disc.2005.12.003","volume":"306","author":"P. Heggernes","year":"2006","unstructured":"Heggernes, P.: Minimal triangulations of graphs: A survey. Discrete Mathematics\u00a0306(3), 297\u2013317 (2006)","journal-title":"Discrete Mathematics"},{"key":"76_CR14","unstructured":"Heggernes, P., Kratsch, D.: Linear-time certifying algorithms for recognizing split graphs and related graph classes. Technical report, 2006-328, UiB (2006)"},{"key":"76_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1007\/11682462_55","volume-title":"LATIN 2006: Theoretical Informatics","author":"P. Heggernes","year":"2006","unstructured":"Heggernes, P., Mancini, F.: Minimal split completions of graphs. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol.\u00a03887, pp. 592\u2013604. Springer, Heidelberg (2006)"},{"key":"76_CR16","doi-asserted-by":"crossref","unstructured":"Heggernes, P., Mancini, F.: A completely dynamic algorithm for split graphs. Technical report, 2006-334, UiB (2006)","DOI":"10.1016\/j.endm.2006.08.060"},{"key":"76_CR17","doi-asserted-by":"crossref","unstructured":"Heggernes, P., Paul, C., Telle, J.A., Villanger, Y.: Interval completion is fixed parameter tractable. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, STOC, pp. 374\u2013381 (2007)","DOI":"10.1145\/1250790.1250847"},{"issue":"2","key":"76_CR18","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0020-0190(89)90070-7","volume":"31","author":"C.W. Ho","year":"1989","unstructured":"Ho, C.W., Lee, R.C.T.: Counting clique trees and computing perfect elimination schemes in parallel. Inf. Process. Lett.\u00a031(2), 61\u201368 (1989)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"76_CR19","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"D.S. Johnson","year":"1988","unstructured":"Johnson, D.S., Papadimitriou, C.H.: On generating all maximal independent sets. Inf. Process. Lett.\u00a027(3), 119\u2013123 (1988)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"76_CR20","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. Comput.\u00a028(5), 1906\u20131922 (1999)","journal-title":"SIAM J. Comput."},{"key":"76_CR21","first-page":"780","volume-title":"35th Annual Symposium on Foundations of Computer Science, FOCS 2004","author":"H. Kaplan","year":"2004","unstructured":"Kaplan, H., Shamir, R., Endre, R.: Tractability of parameterized completion problems on chordal and interval graphs: Minimum fill-in and physical mapping. In: 35th Annual Symposium on Foundations of Computer Science, FOCS 2004, pp. 780\u2013791. IEEE, Los Alamitos (2004)"},{"key":"76_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/11917496_4","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D. Marx","year":"2006","unstructured":"Marx, D.: Chordal deletion is fixed-parameter tractable. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 37\u201348. Springer, Heidelberg (2006)"},{"issue":"3","key":"76_CR23","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1016\/j.tcs.2005.10.008","volume":"351","author":"D. Marx","year":"2006","unstructured":"Marx, D.: Parameterized coloring problems on chordal graphs. Theor. Comput. Sci.\u00a0351(3), 407\u2013424 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"76_CR24","doi-asserted-by":"crossref","unstructured":"Marx, D., Schlotter, I.: Obtaining a planar graph by vertex deletion. In: WG, LNCS (to appear, 2007)","DOI":"10.1007\/978-3-540-74839-7_28"},{"key":"76_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/11604686_19","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S.D. Nikolopoulos","year":"2005","unstructured":"Nikolopoulos, S.D., Palios, L.: Adding an edge in a cograph. In: Kratsch, D. (ed.) WG 2005. LNCS, vol.\u00a03787, pp. 214\u2013226. Springer, Heidelberg (2005)"},{"key":"76_CR26","doi-asserted-by":"publisher","first-page":"622","DOI":"10.1016\/0022-247X(76)90182-7","volume":"54","author":"T. Ohtsuki","year":"1976","unstructured":"Ohtsuki, T., Cheung, L.K., Fujisawa, T.: Minimal triangulation of a graph and optimal pivoting ordering in a sparse matrix. J. Math. Anal. Appl.\u00a054, 622\u2013633 (1976)","journal-title":"J. Math. Anal. Appl."},{"issue":"2","key":"76_CR27","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1137\/1003021","volume":"3","author":"S. Parter","year":"1961","unstructured":"Parter, S.: The use of linear graphs in gauss elimination. SIAM Review\u00a03(2), 119\u2013130 (1961)","journal-title":"SIAM Review"},{"key":"76_CR28","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608044","volume":"8","author":"D.G. Corneil","year":"1987","unstructured":"Corneil, D.G., Arnborg, S., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebraic and Discrete Methods\u00a08, 277\u2013284 (1987)","journal-title":"SIAM J. Algebraic and Discrete Methods"},{"key":"76_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/11917496_10","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"Y. Takenaga","year":"2006","unstructured":"Takenaga, Y., Higashide, K.: Vertex coloring of comparability+ke and -ke graphs. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 102\u2013112. Springer, Heidelberg (2006)"},{"issue":"1","key":"76_CR30","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 Journal on Algebraic and Discrete Methods\u00a02(1), 77\u201379 (1981)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77120-3_76.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:01:29Z","timestamp":1619521289000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77120-3_76"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540771180"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77120-3_76","relation":{},"subject":[]}}