{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T20:14:26Z","timestamp":1774383266139,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,3,28]],"date-time":"2009-03-28T00:00:00Z","timestamp":1238198400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,2]]},"DOI":"10.1007\/s00453-009-9302-7","type":"journal-article","created":{"date-parts":[[2009,3,30]],"date-time":"2009-03-30T14:01:48Z","timestamp":1238421708000},"page":"169-194","source":"Crossref","is-referenced-by-count":21,"title":["Exact Algorithms for L(2,1)-Labeling of Graphs"],"prefix":"10.1007","volume":"59","author":[{"given":"Fr\u00e9d\u00e9ric","family":"Havet","sequence":"first","affiliation":[]},{"given":"Martin","family":"Klazar","sequence":"additional","affiliation":[]},{"given":"Jan","family":"Kratochv\u00edl","sequence":"additional","affiliation":[]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[]},{"given":"Mathieu","family":"Liedloff","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,3,28]]},"reference":[{"key":"9302_CR1","unstructured":"Alon, N., Wormald, N.: High degree graphs contain large-star factors (submitted)"},{"key":"9302_CR2","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T.: Inclusion-exclusion algorithms for counting set partitions. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science 2006, pp.\u00a0575\u2013582 (2006)","DOI":"10.1109\/FOCS.2006.41"},{"key":"9302_CR3","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1093\/comjnl\/47.2.193","volume":"47","author":"H.L. Bodlaender","year":"2004","unstructured":"Bodlaender, H.L., Kloks, T., Tan, R.B., van Leeuwen, J.: Approximations for lambda-colorings of graphs. Comput. J. 47, 193\u2013204 (2004)","journal-title":"Comput. J."},{"key":"9302_CR4","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1137\/S0895480193245339","volume":"9","author":"G.J. Chang","year":"1996","unstructured":"Chang, G.J., Kuo, D.: The L(2,1)-labeling problem on graphs. SIAM J. Discrete Math. 9, 309\u2013316 (1996)","journal-title":"SIAM J. Discrete Math."},{"key":"9302_CR5","series-title":"LNCS","first-page":"537","volume-title":"Proceedings of ISAAC 2001","author":"J. Fiala","year":"2001","unstructured":"Fiala, J., Kratochv\u00edl, J.: Complexity of partial covers of graphs. In: Proceedings of ISAAC 2001. LNCS, vol. 2223, pp. 537\u2013549. Springer, Berlin (2001)"},{"key":"9302_CR6","doi-asserted-by":"crossref","first-page":"89","DOI":"10.7151\/dmgt.1159","volume":"22","author":"J. Fiala","year":"2002","unstructured":"Fiala, J., Kratochv\u00edl, J.: Partial covers of graphs. Discuss. Math. Graph Theory 22, 89\u201399 (2002)","journal-title":"Discuss. Math. Graph Theory"},{"key":"9302_CR7","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/S0166-218X(00)00387-5","volume":"113","author":"J. Fiala","year":"2001","unstructured":"Fiala, J., Kloks, T., Kratochv\u00edl, J.: Fixed-parameter complexity of \u03bb-labelings. Discrete Appl. Math. 113, 59\u201372 (2001)","journal-title":"Discrete Appl. Math."},{"key":"9302_CR8","series-title":"LNCS","first-page":"360","volume-title":"Proceedings of ICALP 2005","author":"J. Fiala","year":"2005","unstructured":"Fiala, J., Golovach, P., Kratochv\u00edl, J.: Distance constrained labelings of graphs of bounded treewidth. In: Proceedings of ICALP 2005. LNCS, vol. 3580, pp. 360\u2013372. Springer, Berlin (2005)"},{"key":"9302_CR9","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.endm.2005.05.012","volume":"19","author":"J. Fiala","year":"2005","unstructured":"Fiala, J., Kratochv\u00edl, J., P\u00f3r, A.: On the computational complexity of partial covers of theta graphs. Electron. Notes Discrete Math. 19, 79\u201385 (2005)","journal-title":"Electron. Notes Discrete Math."},{"key":"9302_CR10","series-title":"LNCS","first-page":"192","volume-title":"Proceedings of ICALP 2005","author":"F. Fomin","year":"2005","unstructured":"Fomin, F., Grandoni, F., Kratsch, D.: Measure and conquer: Domination\u2014a case study. In: Proceedings of ICALP 2005. LNCS, vol. 3380, pp. 192\u2013203. Springer, Berlin (2005)"},{"key":"9302_CR11","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/s00224-007-2007-x","volume":"41","author":"F. Fomin","year":"2007","unstructured":"Fomin, F., Heggernes, P., Kratsch, D.: Exact algorithms for graph homomorphisms. Theory Comput. Syst. 41, 381\u2013393 (2007)","journal-title":"Theory Comput. Syst."},{"key":"9302_CR12","unstructured":"Gon\u00e7alves, D.: On the L(p,1)-labelling of graphs. In: Discrete Mathematics and Theoretical Computer Science Proceedings, vol. AE, pp. 81\u201386"},{"key":"9302_CR13","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1137\/0405048","volume":"5","author":"J.R. Griggs","year":"1992","unstructured":"Griggs, J.R., Yeh, R.K.: Labelling graphs with a condition at distance 2. SIAM J. Discrete Math. 5, 586\u2013595 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"9302_CR14","doi-asserted-by":"crossref","unstructured":"Hasunuma, T., Ishii, T., Ono, H., Uno, Y.: A linear time algorithm for L(2,1)-labeling of trees. arXiv:0810.0906v1 (2008)","DOI":"10.1007\/978-3-642-04128-0_4"},{"key":"9302_CR15","unstructured":"Havet, F., Reed, B., Sereni, J.-S.: L(2,1)-labellings of graphs. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms 2008, pp. 621\u2013630 (2008)"},{"key":"9302_CR16","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P. Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of H-colouring. J. Comb. Theory Ser. B 48, 92\u2013110 (1990)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9302_CR17","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"D.S. Johnson","year":"1988","unstructured":"Johnson, D.S., Yannakakis, M., Papadimitriou, C.H.: On generating all maximal independent sets. Inf. Process. Lett. 27, 119\u2013123 (1988)","journal-title":"Inf. Process. Lett."},{"key":"9302_CR18","doi-asserted-by":"crossref","unstructured":"Koivisto, M.: An O(2 n ) algorithm for graph coloring and other partitioning problems via inclusion-exclusion. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science 2006, pp.\u00a0583\u2013590 (2006)","DOI":"10.1109\/FOCS.2006.11"},{"key":"9302_CR19","doi-asserted-by":"crossref","first-page":"690","DOI":"10.1137\/040619636","volume":"20","author":"D. Kr\u00e1l\u2019","year":"2006","unstructured":"Kr\u00e1l\u2019, D.: Channel assignment problem with variable weights. SIAM J. Discrete Math. 20, 690\u2013704 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"9302_CR20","series-title":"LNCS","first-page":"513","volume-title":"Proceedings of MFCS 2007","author":"J. Kratochv\u00edl","year":"2007","unstructured":"Kratochv\u00edl, J., Kratsch, D., Liedloff, M.: Exact algorithms for L(2,1)-labeling of graphs. In: Proceedings of MFCS 2007. LNCS, vol. 4708, pp. 513\u2013524. Springer, Berlin (2007)"},{"key":"9302_CR21","doi-asserted-by":"crossref","unstructured":"Leese, R.A., Noble, S.D.: Cyclic labellings with constraints at two distances. Electron. J. Comb. 11 (2004) (Research paper 16)","DOI":"10.37236\/1769"},{"key":"9302_CR22","first-page":"177","volume":"69","author":"D. Liu","year":"2003","unstructured":"Liu, D., Zhu, X.: Circular distance two labelings and circular chromatic numbers. Ars Comb. 69, 177\u2013183 (2003)","journal-title":"Ars Comb."},{"key":"9302_CR23","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1137\/S0895480102417768","volume":"19","author":"D. Liu","year":"2005","unstructured":"Liu, D., Zhu, X.: Multilevel distance labelings for paths and cycles. SIAM J. Discrete Math. 19, 610\u2013621 (2005)","journal-title":"SIAM J. Discrete Math."},{"key":"9302_CR24","unstructured":"Roberts, F.S. Private communication to J. Griggs"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9302-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9302-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9302-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T04:37:32Z","timestamp":1589690252000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9302-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3,28]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,2]]}},"alternative-id":["9302"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9302-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,3,28]]}}}