{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:47:29Z","timestamp":1725490049662},"publisher-location":"Berlin, Heidelberg","reference-count":23,"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_10","type":"book-chapter","created":{"date-parts":[[2007,8,17]],"date-time":"2007-08-17T13:44:11Z","timestamp":1187358251000},"page":"75-85","source":"Crossref","is-referenced-by-count":11,"title":["Connected Coloring Completion for General Graphs: Algorithms and Complexity"],"prefix":"10.1007","author":[{"given":"Benny","family":"Chor","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Fellows","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark A.","family":"Ragan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Razgon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frances","family":"Rosamond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sagi","family":"Snir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms\u00a012, 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"key":"10_CR2","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N. Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. Journal of the ACM\u00a042, 844\u2013856 (1995)","journal-title":"Journal of the ACM"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fellows, M., Langston, M., Ragan, M.A., Rosamond, F., Weyer, M.: Quadratic kernelization for convex recoloring of trees. In: Proceedings COCOON 2007, these proceedings (2007)","DOI":"10.1007\/978-3-540-73545-8_11"},{"key":"10_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/11671411_5","volume-title":"Approximation and Online Algorithms","author":"R. Bar-Yehuda","year":"2006","unstructured":"Bar-Yehuda, R., Feldman, I., Rawitz, D.: Improved approximation algorithm for convex recoloring of trees. In: Erlebach, T., Persinao, G. (eds.) WAOA 2005. LNCS, vol.\u00a03879, pp. 55\u201368. Springer, Heidelberg (2006)"},{"key":"10_CR5","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"R.B. Borie","year":"1992","unstructured":"Borie, R.B., Parker, R.G., Tovey, C.A.: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively generated graph families. Algorithmica\u00a07, 555\u2013581 (1992)","journal-title":"Algorithmica"},{"key":"10_CR6","unstructured":"Bodlaender, H.L., Weyer, M.: Convex anc connected recolourings of trees and graphs. Manuscript (2005)"},{"issue":"9","key":"10_CR7","doi-asserted-by":"publisher","first-page":"2443","DOI":"10.1093\/nar\/gkg340","volume":"31","author":"D. Bu","year":"2003","unstructured":"Bu, D., Zhao, Y., Cai, L., Xue, H., Zhu, X., Lu, H., Zhang, J., Sun, S., Ling, L., Zhang, N., Li, G., Chen, R.: Topological structure analysis of the protein-protein interaction network in budding yeast. Nucleic Acids Res.\u00a031(9), 2443\u20132450 (2003)","journal-title":"Nucleic Acids Res."},{"key":"10_CR8","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1109\/CCC.2004.1313826","volume-title":"Proceedings of the 19th Annual IEEE Conference on Computational Complexity","author":"J. Chen","year":"2004","unstructured":"Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D., Kanj, I., Xia, G.: Tight lower bounds for certain parameterized NP-hard problems. In: Proceedings of the 19th Annual IEEE Conference on Computational Complexity, pp. 150\u2013160. IEEE Computer Society Press, Los Alamitos (2004)"},{"key":"10_CR9","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Information and Computation\u00a085, 12\u201375 (1990)","journal-title":"Information and Computation"},{"key":"10_CR10","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":"10_CR11","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"10_CR12","unstructured":"Fellows, M., Giannopoulos, P., Knauer, C., Paul, C., Rosamond, F., Whitesides, S., Yu, N.: The lawnmower and other problems: applications of MSO logic in geometry, Manuscript (2007)"},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"Gramm, J., Nickelsen, A., Tantau, T.: Fixed-parameter algorithms in phylogenetics. Manuscript (2006)","DOI":"10.1093\/comjnl\/bxm049"},{"key":"10_CR14","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1093\/molbev\/msj030","volume":"23","author":"D.H. Huson","year":"2006","unstructured":"Huson, D.H., Bryant, D.: Application of phylogenetic networks in evolutionary studies. Mol. Biol. E\u00a023, 254\u2013267 (2006)","journal-title":"Mol. Biol. E"},{"key":"10_CR15","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1093\/bioinformatics\/14.1.68","volume":"14","author":"D.H. Huson","year":"1998","unstructured":"Huson, D.H.: SplitsTree: a program for analyzing and visualizing evolutionary data. Bioinfomatics\u00a014, 68\u201373 (1998)","journal-title":"Bioinfomatics"},{"key":"10_CR16","doi-asserted-by":"publisher","first-page":"11394","DOI":"10.1073\/pnas.1534710100","volume":"100","author":"B.P. Kelley","year":"2003","unstructured":"Kelley, B.P., Sharan, R., Karp, R.M., Sittler, T., Root, D.E., Stockwell, B.R., Ideker, T.: Conserved pathways within bacteria and yeast as revealed by global protein network alignment. Proc. Natl. Acad. Sci. USA\u00a0100, 11394\u201311399 (2003)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"10_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1007\/11534273_20","volume-title":"Algorithms and Data Structures","author":"S. Moran","year":"2005","unstructured":"Moran, S., Snir, S.: Convex recolorings of strings and trees: definitions, hardness results and algorithms. To appear in Journal of Computer and System Sciences. In: Dehne, F., L\u00f3pez-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol.\u00a03608, pp. 218\u2013232. Springer, Heidelberg (2005) A preliminary version appeared"},{"key":"10_CR18","unstructured":"Moran, S., Snir, S., Sung, W.: Partial convex recolorings of trees and galled networks. Manuscript (2006)"},{"key":"10_CR19","doi-asserted-by":"crossref","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":"10_CR20","volume-title":"A hypergraph model for the yeast protein complex network","author":"E. Ramadan","year":"2004","unstructured":"Ramadan, E., Tarafdar, A., Pothen, A.: A hypergraph model for the yeast protein complex network. In: Fourth IEEE International Workshop on High Performance Computational Biology, Santa Fe, NM, April 26, 2004. IEEE Computer Society Press, Los Alamitos (2004)"},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"Rual, J.F., Venkatesan, K., Hao, T., Hirozane-Kishikawa, T., Dricot, A., Li, N., Berriz, G.F., Gibbons, F.D., Dreze, M., Ayivi-Guedehoussou, N., Klitgord, N., Simon, C., Boxem, M., Milstein, S., Rosenberg, J., Goldberg, D.S., Zhang, L.V., Wong, S.L., Franklin, G., Li, S., Albala, J.S., Lim, J., Fraughton, C., Llamosas, E., Cevik, S., Bex, C., Lamesch, P., Sikorski, R.S., Vandenhaute, J., Zoghbi, H.Y., Smolyar, A., Bosak, S., Sequerra, R., Doucette-Stamm, L., Cusick, M.E., Hill, D.E., Roth, F.P., Vidal, M.: Nature 437, 1173\u20131178 (2005)","DOI":"10.1038\/nature04209"},{"issue":"12","key":"10_CR22","doi-asserted-by":"publisher","first-page":"1257","DOI":"10.1038\/82360","volume":"18","author":"B. Schwikowski","year":"2000","unstructured":"Schwikowski, B., Uetz, P., Fields, S.: A network of protein-protein interactions in yeast. Nature Biotechnology\u00a018(12), 1257\u20131261 (2000)","journal-title":"Nature Biotechnology"},{"key":"10_CR23","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1142\/S0219633602000117","volume":"1","author":"S. Viveshwara","year":"2002","unstructured":"Viveshwara, S., Brinda, K.V., Kannan, N.: Protein structure: insights from graph theory. J. Theoretical and Computational Chemistry\u00a01, 187\u2013211 (2002)","journal-title":"J. Theoretical and Computational Chemistry"}],"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_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:17:43Z","timestamp":1619518663000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73545-8_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540735441","9783540735458"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73545-8_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}