{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:46:38Z","timestamp":1725489998185},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540735441"},{"type":"electronic","value":"9783540735458"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73545-8_40","type":"book-chapter","created":{"date-parts":[[2007,8,17]],"date-time":"2007-08-17T13:44:11Z","timestamp":1187358251000},"page":"406-416","source":"Crossref","is-referenced-by-count":4,"title":["Single-Edge Monotonic Sequences of Graphs and Linear-Time Algorithms for Minimal Completions and Deletions"],"prefix":"10.1007","author":[{"given":"Pinar","family":"Heggernes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charis","family":"Papadopoulos","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: Proceedings of STOC 2005 - 37th Annual Symposium on Theory of Computing, 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":"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":"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","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":"40_CR8","unstructured":"Chv\u00e1tal, V., Hammer, P.L.: Set-packing and threshold graphs. Univ. Waterloo Res. Report, CORR 73\u201321 (1973)"},{"key":"40_CR9","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0166-218X(88)90075-3","volume":"20","author":"P.M. Dearing","year":"1988","unstructured":"Dearing, P.M., Shier, D.R., Warner, D.D.: Maximal chordal subgraphs. Disc. Appl. Math.\u00a020, 181\u2013190 (1988)","journal-title":"Disc. Appl. Math."},{"key":"40_CR10","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1137\/S0895480197328771","volume":"20","author":"H. Djidjev","year":"2006","unstructured":"Djidjev, H.: A linear algorithm for finding a maximal planar subgraph. SIAM J. Disc. Math.\u00a020, 444\u2013462 (2006)","journal-title":"SIAM J. Disc. Math."},{"key":"40_CR11","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)"},{"key":"40_CR12","first-page":"311","volume":"19","author":"S. F\u00f6ldes","year":"1977","unstructured":"F\u00f6ldes, S., Hammer, P.L.: Split graphs. Congressus Numer.\u00a019, 311\u2013315 (1977)","journal-title":"Congressus Numer."},{"key":"40_CR13","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M. Garey","year":"1976","unstructured":"Garey, M., Johnson, D., Stockmeyer, L.: Some simplified NP-complete graph problems. Theoretical Computer Science\u00a01, 237\u2013267 (1976)","journal-title":"Theoretical Computer Science"},{"key":"40_CR14","series-title":"Annals of Discrete Mathematics","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edn. Annals of Discrete Mathematics, vol.\u00a057. Elsevier, Amsterdam (2004)","edition":"2"},{"key":"40_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":"40_CR16","doi-asserted-by":"crossref","unstructured":"Heggernes, P., Mancini, F.: A completely dynamic algorithm for split graphs. Reports in Informatics 334, University of Bergen, Norway (2006)","DOI":"10.1016\/j.endm.2006.08.060"},{"key":"40_CR17","unstructured":"Heggernes, P., Papadopoulos, C.: Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions. Reports in Informatics 345, University of Bergen, Norway (2007)"},{"key":"40_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"2007","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: Towards better understanding of profile and pathwidth. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 2007\u20132024. Springer, Heidelberg (2007)"},{"key":"40_CR19","doi-asserted-by":"publisher","first-page":"900","DOI":"10.1137\/S0895480104445010","volume":"19","author":"P. Heggernes","year":"2005","unstructured":"Heggernes, P., Telle, J.A., Villanger, Y.: Computing minimal triangulations in time O(n \u03b1 logn)\u2009=\u2009o(n 2.376). SIAM J. Disc. Math.\u00a019, 900\u2013913 (2005)","journal-title":"SIAM J. Disc. Math."},{"key":"40_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1007\/11533719_80","volume-title":"Computing and Combinatorics","author":"W.-L. Hsu","year":"2005","unstructured":"Hsu, W.-L.: A linear time algorithm for finding a maximal planar subgraph based on PC-trees. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 787\u2013797. Springer, Heidelberg (2005)"},{"issue":"5","key":"40_CR21","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":"40_CR22","first-page":"82","volume-title":"An NP-complete problem on interval graphs","author":"T. Kashiwabara","year":"1979","unstructured":"Kashiwabara, T., Fujisawa, T.: An NP-complete problem on interval graphs. IEEE Symp. of Circuits and Systems, pp. 82\u201383. IEEE Computer Society Press, Los Alamitos (1979)"},{"key":"40_CR23","series-title":"Annals of Discrete Mathematics 56","volume-title":"Threshold graphs and related topics","author":"N. Mahadev","year":"1995","unstructured":"Mahadev, N., Peled, U.: Threshold graphs and related topics. Annals of Discrete Mathematics 56. North Holland, Amsterdam (1995)"},{"key":"40_CR24","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/j.dam.2004.10.001","volume":"146","author":"D. Meister","year":"2005","unstructured":"Meister, D.: Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs. Disc. Appl. Math.\u00a0146, 193\u2013218 (2005)","journal-title":"Disc. Appl. Math."},{"key":"40_CR25","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_CR26","doi-asserted-by":"publisher","first-page":"1003","DOI":"10.1016\/j.dam.2005.09.010","volume":"154","author":"S.-L. Peng","year":"2006","unstructured":"Peng, S.-L., Chen, C.-K.: On the interval completion of chordal graphs. Disc. Appl. Math.\u00a0154, 1003\u20131010 (2006)","journal-title":"Disc. Appl. Math."},{"key":"40_CR27","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":"40_CR28","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_CR29","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":"40_CR30","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1137\/0210022","volume":"10","author":"M. Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Node deletion problems on bipartite graphs. SIAM J.\u00a0Comput.\u00a010, 310\u2013327 (1981)","journal-title":"SIAM J.\u00a0Comput."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73545-8_40.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:17:57Z","timestamp":1619518677000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73545-8_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540735441","9783540735458"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73545-8_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}