{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T12:43:00Z","timestamp":1725453780104},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642387678"},{"type":"electronic","value":"9783642387685"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38768-5_54","type":"book-chapter","created":{"date-parts":[[2013,5,17]],"date-time":"2013-05-17T00:31:28Z","timestamp":1368750688000},"page":"614-625","source":"Crossref","is-referenced-by-count":5,"title":["On the Complexity of Solving or Approximating Convex Recoloring Problems"],"prefix":"10.1007","author":[{"given":"Manoel B.","family":"Camp\u00ealo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cristiana G.","family":"Huiban","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rudini M.","family":"Sampaio","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoshiko","family":"Wakabayashi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"54_CR1","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/1150334.1150336","volume":"2","author":"N. Alon","year":"2006","unstructured":"Alon, N., Moshkovitz, D., Safra, S.: Algorithmic construction of sets for k-restrictions. ACM Transactions on Algorithms\u00a02, 153\u2013177 (2006)","journal-title":"ACM Transactions on Algorithms"},{"key":"54_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0166-218X(97)90120-7","volume":"84","author":"L. Babel","year":"1998","unstructured":"Babel, L., Olariu, S.: On the structure of graphs with few P\n                  4\u2032s. Discrete Appl. Math.\u00a084, 1\u201313 (1998)","journal-title":"Discrete Appl. Math."},{"key":"54_CR3","unstructured":"Baumann, S.: A linear algorithm for the homogeneous decomposition of graphs, Report No. M-9615, Zentrum f\u00fcr Mathematik, Technische Universit\u00e4t M\u00fcnchen (1996)"},{"key":"54_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00224-007-9069-7","volume":"43","author":"R. Bar-Yehuda","year":"2008","unstructured":"Bar-Yehuda, R., Feldman, I., Rawitz, D.: Improved approximation algorithm for convex recoloring of trees. Theor. Comp. Sys.\u00a043, 3\u201318 (2008)","journal-title":"Theor. Comp. Sys."},{"issue":"2","key":"54_CR5","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1007\/s00453-010-9404-2","volume":"61","author":"H.L. Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Fellows, M.R., Langston, M.A., Ragan, M.A., Rosamond, F.A., Weyer, M.: Quadratic kernelization for convex recoloring of trees. Algorithmica\u00a061(2), 362\u2013388 (2011)","journal-title":"Algorithmica"},{"key":"54_CR6","doi-asserted-by":"crossref","unstructured":"Camp\u00ealo, M.B., Lima, K.R., Moura, P.F.S., Wakabayashi, Y.: Polyhedral studies on the convex recoloring problem (2012), accepted to VII Latin-American Algorithms, Graphs and Optimization Symposium (2013)","DOI":"10.1016\/j.endm.2013.10.036"},{"key":"54_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-540-73545-8_10","volume-title":"Computing and Combinatorics","author":"B. Chor","year":"2007","unstructured":"Chor, B., Fellows, M., Ragan, M.A., Razgon, I., Rosamond, F., Snir, S.: Connected coloring completion for general graphs: Algorithms and complexity. In: Lin, G. (ed.) COCOON 2007. LNCS, vol.\u00a04598, pp. 75\u201385. Springer, Heidelberg (2007)"},{"key":"54_CR8","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear steiner tree problem in NP-complete. SIAM Journal of Applied Mathematics\u00a032, 826\u2013834 (1977)","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"54_CR9","doi-asserted-by":"publisher","first-page":"810","DOI":"10.1016\/j.dam.2011.09.022","volume":"160","author":"F. Kammer","year":"2012","unstructured":"Kammer, F., Tholey, T.: The complexity of minimum convex coloring. Discrete Appl. Math.\u00a0160, 810\u2013833 (2012)","journal-title":"Discrete Appl. Math."},{"key":"54_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1007\/978-3-642-02882-3_39","volume-title":"Computing and Combinatorics","author":"I.A. Kanj","year":"2009","unstructured":"Kanj, I.A., Kratsch, D.: Convex recoloring revisited: Complexity and exact algorithms. In: Ngo, H.Q. (ed.) COCOON 2009. LNCS, vol.\u00a05609, pp. 388\u2013397. Springer, Heidelberg (2009)"},{"key":"54_CR11","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0166-218X(92)90036-A","volume":"35","author":"B. Jamison","year":"1992","unstructured":"Jamison, B., Olariu, S.: A tree representation for P\n                  4-sparse graphs. Discrete Appl. Math.\u00a035, 115\u2013129 (1992)","journal-title":"Discrete Appl. Math."},{"key":"54_CR12","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/j.endm.2011.05.029","volume":"37","author":"K.R. Lima","year":"2011","unstructured":"Lima, K.R., Wakabayashi, Y.: Convex recoloring of paths. Electronic Notes in Discrete Mathematics\u00a037, 165\u2013170 (2011)","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"54_CR13","doi-asserted-by":"publisher","first-page":"1078","DOI":"10.1016\/j.jcss.2007.03.006","volume":"73","author":"S. Moran","year":"2007","unstructured":"Moran, S., Snir, S.: Efficient approximation of convex recolorings. J. Comput. Syst. Sci.\u00a073, 1078\u20131089 (2007)","journal-title":"J. Comput. Syst. Sci."},{"key":"54_CR14","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1016\/j.jcss.2007.10.003","volume":"74","author":"S. Moran","year":"2008","unstructured":"Moran, S., Snir, S.: Convex recolorings of strings and trees: Definitions, hardness results and algorithms. J. Comput. Syst. Sci.\u00a074, 850\u2013869 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"54_CR15","doi-asserted-by":"crossref","unstructured":"Moran, S., Snir, S., Sung, W.-K.: Partial convex recolorings of trees and galled networks: tight upper and lower bounds. ACM Trans. Algorithms 7 (2011)","DOI":"10.1145\/2000807.2000810"},{"key":"54_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1007\/978-3-540-79228-4_43","volume-title":"Theory and Applications of Models of Computation","author":"O. Ponta","year":"2008","unstructured":"Ponta, O., H\u00fcffner, F., Niedermeier, R.: Speeding up dynamic programming for some NP-hard graph recoloring problems. In: Agrawal, M., Du, D.-Z., Duan, Z., Li, A. (eds.) TAMC 2008. LNCS, vol.\u00a04978, pp. 490\u2013501. Springer, Heidelberg (2008)"},{"key":"54_CR17","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proc. of the 29th Annual ACM Symposium on Theory of Computing, pp. 475\u2013484 (1997)","DOI":"10.1145\/258533.258641"},{"issue":"2","key":"54_CR18","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.ipl.2007.05.007","volume":"104","author":"I. Razgon","year":"2007","unstructured":"Razgon, I.: A \n                    \n                      \n                    \n                    $2\\sp{O(k)}{\\rm poly}(n)$\n                   algorithm for the parameterized convex recoloring problem. Inform. Process. Lett.\u00a0104(2), 53\u201358 (2007)","journal-title":"Inform. Process. Lett."},{"key":"54_CR19","unstructured":"Sales, C.L., Maia, A.K., Martins, N., Sampaio, R.M.: Restricted Coloring Problems on graphs with few P\n                  4\u2019s. Annals of Operations Research (to appear)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38768-5_54","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,12]],"date-time":"2019-05-12T22:06:10Z","timestamp":1557698770000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38768-5_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642387678","9783642387685"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38768-5_54","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}