{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T17:10:11Z","timestamp":1738257011051,"version":"3.35.0"},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540693109"},{"type":"electronic","value":"9783540693116"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-69311-6_17","type":"book-chapter","created":{"date-parts":[[2008,6,6]],"date-time":"2008-06-06T11:17:46Z","timestamp":1212751066000},"page":"147-158","source":"Crossref","is-referenced-by-count":2,"title":["Characterizing and Computing Minimal Cograph Completions"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Lokshtanov","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"}]}],"member":"297","reference":[{"key":"17_CR1","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1016\/j.disc.2005.12.002","volume":"306","author":"A. Berry","year":"2006","unstructured":"Berry, A., Heggernes, P., Villanger, Y.: A vertex incremental approach for dynamically maintaining chordal graphs. Discrete Math.\u00a0306, 318\u2013336 (2006)","journal-title":"Discrete Math."},{"key":"17_CR2","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0304-3975(99)00126-7","volume":"250","author":"J. Blair","year":"2001","unstructured":"Blair, J., Heggernes, P., Telle, J.A.: A practical algorithm for making filled graphs minimal. Theoretical Computer Science\u00a0250, 125\u2013141 (2001)","journal-title":"Theoretical Computer Science"},{"key":"17_CR3","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":"17_CR4","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. In: SIAM Monographs on Discrete Mathematics and Applications (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"17_CR5","doi-asserted-by":"publisher","first-page":"1824","DOI":"10.1016\/j.dam.2006.03.031","volume":"154","author":"P. Burzyn","year":"2006","unstructured":"Burzyn, P., Bonomo, F., Dur\u00e1n, G.: NP-completeness results for edge modification problems. Disc. Appl. Math.\u00a0154, 1824\u20131844 (2006)","journal-title":"Disc. Appl. Math."},{"key":"17_CR6","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"D.G. Corneil","year":"1981","unstructured":"Corneil, D.G., Lerchs, H., Stewart, L.K.: Complement reducible graphs. Disc. Appl. Math.\u00a03, 163\u2013174 (1981)","journal-title":"Disc. Appl. Math."},{"key":"17_CR7","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"D.G. Corneil","year":"1985","unstructured":"Corneil, D.G., Perl, Y., Stewart, L.K.: A linear recognition algorithm for cographs. SIAM J.\u00a0Comput.\u00a014, 926\u2013934 (1985)","journal-title":"SIAM J.\u00a0Comput."},{"key":"17_CR8","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1109\/31.1748","volume":"35","author":"E. El-Mallah","year":"1988","unstructured":"El-Mallah, E., Colbourn, C.: The complexity of some edge deletion problems. IEEE Transactions on Circuits and Systems\u00a035, 354\u2013362 (1988)","journal-title":"IEEE Transactions on Circuits and Systems"},{"key":"17_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1007\/978-3-540-27836-8_49","volume-title":"Automata, Languages and Programming","author":"F.V. Fomin","year":"2004","unstructured":"Fomin, F.V., Kratsch, D., Todinca, I.: Exact (Exponential) Algorithms for Treewidth and Minimum Fill-In. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 568\u2013580. Springer, Heidelberg (2004)"},{"issue":"1","key":"17_CR10","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":"17_CR11","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, 449\u2013473 (1995)","journal-title":"J. Algorithms"},{"key":"17_CR12","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":"17_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/11940128_43","volume-title":"Algorithms and Computation","author":"P. Heggernes","year":"2006","unstructured":"Heggernes, P., Mancini, F., Papadopoulos, C.: Making Arbitrary Graphs Transitively Orientable: Minimal Comparability Completions. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol.\u00a04288, pp. 419\u2013428. Springer, Heidelberg (2006)"},{"key":"17_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1007\/978-3-540-73545-8_40","volume-title":"Computing and Combinatorics","author":"P. Heggernes","year":"2007","unstructured":"Heggernes, P., Papadopoulos, C.: Single-Edge Monotonic Sequences of Graphs and Linear-Time Algorithms for Minimal Completions and Deletions. In: Lin, G. (ed.) COCOON 2007. LNCS, vol.\u00a04598, pp. 406\u2013416. Springer, Heidelberg (2007)"},{"key":"17_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/978-3-540-70918-3_21","volume-title":"STACS 2007","author":"P. Heggernes","year":"2007","unstructured":"Heggernes, P., Suchan, K., Todinca, I., Villanger, Y.: Characterizing Minimal Interval Completions. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 236\u2013247. Springer, Heidelberg (2007)"},{"key":"17_CR16","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: Proceedings of SODA 2005 - 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 907\u2013916 (2005)","DOI":"10.1137\/S0895480104445010"},{"key":"17_CR17","unstructured":"Kashiwabara, T., Fujisawa, T.: An NP-complete problem on interval graphs. In: IEEE Symp. of Circuits and Systems, pp. 82\u201383 (1979)"},{"key":"17_CR18","doi-asserted-by":"crossref","unstructured":"Natanzon, A., Shamir, R., Sharan, R.: A polynomial approximation algorithm for the minimum fill-in problem. In: Proceedings of STOC 1998 - 30th Annual ACM Symposium on Theory of Computing, pp. 41\u201347 (1998)","DOI":"10.1145\/276698.276710"},{"issue":"4","key":"17_CR19","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."},{"key":"17_CR20","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: Proceedings of FOCS 2004 - 35th Annual Symposium on Foundations of Computer Science, pp. 780\u2013791 (2004)","DOI":"10.1109\/SFCS.1994.365715"},{"key":"17_CR21","doi-asserted-by":"crossref","unstructured":"Heggernes, P., Paul, C., Telle, J.A., Villanger, Y.: Interval Completion is Fixed Parameter Tractable. In: Proceedings of STOC 2007 - 39th Annual ACM Symposium on Theory of Computing, pp. 374\u2013381 (2007)","DOI":"10.1145\/1250790.1250847"},{"issue":"4","key":"17_CR22","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/s00453-005-1180-z","volume":"44","author":"M. Dom","year":"2006","unstructured":"Dom, M., Guo, J., H\u00fcffner, F., Niedermeier, R.: Error Compensation in Leaf Power Problems. Algorithmica\u00a044(4), 363\u2013381 (2006)","journal-title":"Algorithmica"},{"key":"17_CR23","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":"17_CR24","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":"17_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/11917496_20","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"I. Rapaport","year":"2006","unstructured":"Rapaport, I., Suchan, K., Todinca, I.: Minimal Proper Interval Completions. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 217\u2013228. Springer, Heidelberg (2006)"},{"key":"17_CR26","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/B978-1-4832-3187-7.50018-0","volume-title":"Graph Theory and Computing","author":"D.J. Rose","year":"1972","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)"},{"key":"17_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/11940128_52","volume-title":"Algorithms and Computation","author":"K. Suchan","year":"2006","unstructured":"Suchan, K., Todinca, I.: Minimal Interval Completion Through Graph Exploration. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol.\u00a04288, pp. 517\u2013526. Springer, Heidelberg (2006)"},{"issue":"5","key":"17_CR28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00008","volume":"2","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L., Kloks, T., Kratsch, D., M\u00fcller, H.: Treewidth and Minimum Fill-in on d-Trapezoid Graphs. J. Graph Algorithms Appl.\u00a02(5), 1\u201328 (1998)","journal-title":"J. Graph Algorithms Appl."},{"issue":"2","key":"17_CR29","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/S0304-3975(96)00206-X","volume":"175","author":"T. Kloks","year":"1997","unstructured":"Kloks, T., Kratsch, D., Spinrad, J.: On treewidth and minimum fill-in of asteroidal triple-free graphs. Theor. Comput. Sci.\u00a0175(2), 309\u2013335 (1997)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"17_CR30","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/S0166-218X(99)00146-8","volume":"99","author":"H.J. Broersma","year":"2000","unstructured":"Broersma, H.J., Dahlhaus, E., Kloks, T.: A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs. Discrete Applied Mathematics\u00a099(1), 367\u2013400 (2000)","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"17_CR31","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1006\/jagm.1998.0936","volume":"28","author":"T. Kloks","year":"1998","unstructured":"Kloks, T., Kratsch, D., Wong, C.K.: Minimum Fill-in on Circle and Circular-Arc Graphs. Journal of Algorithms\u00a028(2), 272\u2013289 (1998)","journal-title":"Journal of Algorithms"},{"key":"17_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1007\/978-3-540-77120-3_76","volume-title":"Algorithms and Computation","author":"F. Mancini","year":"2007","unstructured":"Mancini, F.: Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol.\u00a04835, pp. 881\u2013892. Springer, Heidelberg (2007)"},{"key":"17_CR33","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."},{"key":"17_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1007\/978-3-540-39890-5_6","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"A. Berry","year":"2003","unstructured":"Berry, A., Heggernes, P., Simonet, G.: The Minimum Degree Heuristic and the Minimal Triangulation Process. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 58\u201370. Springer, Heidelberg (2003)"},{"issue":"1","key":"17_CR35","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(1), 212\u2013232 (2001)","journal-title":"SIAM J. Comput."},{"key":"17_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"800","DOI":"10.1007\/11682462_73","volume-title":"LATIN 2006: Theoretical Informatics","author":"Y. Villanger","year":"2006","unstructured":"Villanger, Y.: Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol.\u00a03887, pp. 800\u2013811. Springer, Heidelberg (2006)"},{"key":"17_CR37","unstructured":"Heggernes, P., Mancini, F.: Dinamically Mantaining Split Graphs. Tech report: http:\/\/www.ii.uib.no\/~federico\/papers\/dynsplit-rev2.pdf"},{"key":"17_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/978-3-540-39890-5_11","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"A. Bretscher","year":"2003","unstructured":"Bretscher, A., Corneil, D.G., Habib, M., Paul, C.: A Simple Linear Time LexBFS Cograph Recognition Algorithm. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 119\u2013130. Springer, Heidelberg (2003)"},{"key":"17_CR39","first-page":"71","volume-title":"The design and analysis of computer algorithms","author":"A.V. Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, I.E., Ullman, J.D.: The design and analysis of computer algorithms, ex. 2.12, p. 71. Addison-Wesley, Reading (1974)"}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69311-6_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T16:32:29Z","timestamp":1738254749000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-69311-6_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540693109","9783540693116"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69311-6_17","relation":{},"subject":[]}}