{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T05:29:44Z","timestamp":1740115784323,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642130724"},{"type":"electronic","value":"9783642130731"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"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":[[2010]]},"DOI":"10.1007\/978-3-642-13073-1_12","type":"book-chapter","created":{"date-parts":[[2010,5,10]],"date-time":"2010-05-10T08:09:58Z","timestamp":1273478998000},"page":"120-130","source":"Crossref","is-referenced-by-count":3,"title":["A Parameterized Algorithm for Chordal Sandwich"],"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":"Jesper","family":"Nederlof","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yngve","family":"Villanger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/3-540-55719-9_80","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"1992","unstructured":"Bodlaender, H.L., Fellows, M.R., Warnow, T.: Two strikes against perfect phylogeny. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol.\u00a0623, pp. 273\u2013283. Springer, Heidelberg (1992)"},{"issue":"1-2","key":"12_CR2","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0304-3975(98)00342-9","volume":"244","author":"H.L. Bodlaender","year":"2000","unstructured":"Bodlaender, H.L., Fellows, M.R., Hallett, M.T., Wareham, T., Warnow, T.: The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs. Theor. Comput. Sci.\u00a0244(1-2), 167\u2013188 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"12_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/978-3-540-92182-0_27","volume-title":"Algorithms and Computation","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Heggernes, P., Villanger, Y.: Faster parameterized algorithms for Minimum Fill-In. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol.\u00a05369, pp. 282\u2013293. Springer, Heidelberg (2008)"},{"key":"12_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/978-3-540-70575-8_46","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On Problems without Polynomial Kernels (Extended Abstract). In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 563\u2013574. Springer, Heidelberg (2008)"},{"key":"12_CR5","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1137\/S0097539799359683","volume":"31","author":"V. Bouchitt\u00e9","year":"2002","unstructured":"Bouchitt\u00e9, V., Todinca, I.: Treewidth and minimum fill-in: Grouping the minimal separators. SIAM Journal on Computing\u00a031, 212\u2013232 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"12_CR6","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","volume":"9","author":"P. Buneman","year":"1974","unstructured":"Buneman, P.: A characterization of rigid circuit graphs. Disc. Math.\u00a09, 205\u2013212 (1974)","journal-title":"Disc. Math."},{"key":"12_CR7","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, 171\u2013176 (1996)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"12_CR8","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. Inf. Process. Lett.\u00a067(1), 31\u201335 (1998)","journal-title":"Inf. Process. Lett."},{"key":"12_CR9","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. Anh. Math. Sem. Univ. Hamburg\u00a025, 71\u201376 (1961)","journal-title":"Anh. Math. Sem. Univ. Hamburg"},{"key":"12_CR10","series-title":"Monographs in Computer Science","doi-asserted-by":"publisher","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. Monographs in Computer Science. Springer, Heidelberg (1999)"},{"key":"12_CR11","unstructured":"Fernau, H., Fomin, F., Lokshtanov, D., Raible, D., Saurabh, S., Villanger, Y.: Kernel(s) for Problems With no Kernel: On Out-Trees With Many Leaves. In: STACS 2009, Dagstuhl Seminar Proceedings, vol.\u00a009001, pp. 421\u2013432 (2009)"},{"key":"12_CR12","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"12_CR13","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"},{"key":"12_CR14","unstructured":"Fomin, F.V., Villanger, Y.: Finding Induced Subgraphs via Minimal Triangulations. In: STACS 2010. INRIA\u00a000455360-1, pp. 383\u2013394 (2010)"},{"key":"12_CR15","volume-title":"Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics","author":"M.C. Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics, 2nd edn., vol.\u00a057. Elsevier, Amsterdam (2004)","edition":"2"},{"issue":"3","key":"12_CR16","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. J. Algorithms\u00a019(3), 449\u2013473 (1995)","journal-title":"J. Algorithms"},{"key":"12_CR17","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 and Combinatorics\u00a014, 223\u2013239 (1998)","journal-title":"Graphs and Combinatorics"},{"issue":"16","key":"12_CR18","doi-asserted-by":"publisher","first-page":"2030","DOI":"10.1016\/j.disc.2005.12.048","volume":"307","author":"M. Habib","year":"2007","unstructured":"Habib, M., Kelly, D., Lebhar, E., Paul, C.: Can transitive orientation make sandwich problems easier? Disc. Math.\u00a0307(16), 2030\u20132041 (2007)","journal-title":"Disc. Math."},{"key":"12_CR19","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. Disc. Math.\u00a0306, 297\u2013317 (2006)","journal-title":"Disc. Math."},{"key":"12_CR20","doi-asserted-by":"crossref","unstructured":"Heggernes, P., Telle, J.A., Villanger, Y.: Computing Minimal Triangulations in Time O(n \u03b1 logn)\u2009=\u2009o(n 2.376). In: SODA 2005, pp. 907\u2013916 (2005)","DOI":"10.1137\/S0895480104445010"},{"issue":"1-3","key":"12_CR21","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.tcs.2007.04.007","volume":"381","author":"C.M.H. de Figueiredo","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. Theor. Comput. Sci.\u00a0381(1-3), 57\u201367 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"1-3","key":"12_CR22","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/S0166-218X(01)00246-3","volume":"121","author":"C.M.H. de Figueiredo","year":"2002","unstructured":"de Figueiredo, C.M.H., Klein, S., Vuskovic, K.: The graph sandwich problem for 1-join composition is NP-complete. Disc. Appl. Math.\u00a0121(1-3), 73\u201382 (2002)","journal-title":"Disc. Appl. Math."},{"key":"12_CR23","doi-asserted-by":"crossref","unstructured":"Kaplan, H., Shamir, R., Tarjan, R.E.: Tractability of parameterized completion problems on chordal and interval graphs: Minimum fill-in and physical mapping. In: FOCS 1994, pp. 780\u2013791 (1994)","DOI":"10.1109\/SFCS.1994.365715"},{"key":"12_CR24","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. Computing\u00a028, 1906\u20131922 (1999)","journal-title":"SIAM J. Computing"},{"key":"12_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/978-3-540-74456-6_26","volume-title":"Mathematical Foundations of Computer Science 2007","author":"D. Lokshtanov","year":"2007","unstructured":"Lokshtanov, D.: On the Complexity of Computing Treelength. In: Ku\u010dera, L., Ku\u010dera, A. (eds.) MFCS 2007. LNCS, vol.\u00a04708, pp. 276\u2013287. Springer, Heidelberg (2007)"},{"key":"12_CR26","unstructured":"Marx, D.: Chordal Deletion Is Fixed-Parameter Tractable. Algorithmica (to appear)"},{"key":"12_CR27","doi-asserted-by":"publisher","first-page":"1067","DOI":"10.1137\/S0097539798336073","volume":"30","author":"A. Natanzon","year":"2000","unstructured":"Natanzon, A., Shamir, R., Sharan, R.: A polynomial approximation algorithm for the minimum fill-in problem. SIAM J. Computing\u00a030, 1067\u20131079 (2000)","journal-title":"SIAM J. Computing"},{"key":"12_CR28","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"12_CR29","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/S0166-218X(97)00041-3","volume":"79","author":"A. Parra","year":"1997","unstructured":"Parra, A., Scheffler, P.: Characterizations and algorithmic applications of chordal graph embeddings. Disc. Appl. Math.\u00a079, 171\u2013188 (1997)","journal-title":"Disc. Appl. Math."},{"key":"12_CR30","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D.J. Rose","year":"1976","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput.\u00a05, 266\u2013283 (1976)","journal-title":"SIAM J. Comput."},{"key":"12_CR31","unstructured":"Schaefer, M.: The graph sandwich problem for a coNP property. Tech.\u00a0Report TR 06-011, DePaul University (2006)"},{"key":"12_CR32","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/BF02618470","volume":"9","author":"M. Steel","year":"1992","unstructured":"Steel, M.: The complexity of reconstructing trees from qualitative characters and subtrees. J. of Classification\u00a09, 91\u2013116 (1992)","journal-title":"J. of Classification"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13073-1_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T18:50:38Z","timestamp":1740077438000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13073-1_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642130724","9783642130731"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13073-1_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}