{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:45:22Z","timestamp":1759063522915},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642346101"},{"type":"electronic","value":"9783642346118"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-34611-8_15","type":"book-chapter","created":{"date-parts":[[2012,10,22]],"date-time":"2012-10-22T08:42:25Z","timestamp":1350895345000},"page":"126-137","source":"Crossref","is-referenced-by-count":1,"title":["Determining the L(2,1)-Span in Polynomial Space"],"prefix":"10.1007","author":[{"given":"Konstanty","family":"Junosza-Szaniawski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Kratochv\u00edl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathieu","family":"Liedloff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"Rz\u0105\u017cewski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"15_CR1","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A. Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set Partitioning via Inclusion-Exclusion. SIAM J. Comput.\u00a039, 546\u2013563 (2009)","journal-title":"SIAM J. Comput."},{"key":"15_CR2","doi-asserted-by":"publisher","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. Computer Journal\u00a047, 193\u2013204 (2004)","journal-title":"Computer Journal"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Kratsch, D.: An exact algorithm for graph coloring with polynomial memory. UU-CS 2006-015 (2006)","DOI":"10.1007\/11841036_60"},{"issue":"8","key":"15_CR4","doi-asserted-by":"publisher","first-page":"1344","DOI":"10.1093\/comjnl\/bxr037","volume":"54","author":"T. Calamoneri","year":"2011","unstructured":"Calamoneri, T.: The L(h, k)-Labelling Problem: An Updated Survey and Annotated Bibliography. Computer Journal\u00a054(8), 1344\u20131371 (2011)","journal-title":"Computer Journal"},{"key":"15_CR5","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1016\/j.ipl.2011.05.008","volume":"111","author":"M. Cygan","year":"2011","unstructured":"Cygan, M., Kowalik, L.: Channel assignment via fast zeta transform. Inf. Proc. Letters\u00a0111, 727\u2013730 (2011)","journal-title":"Inf. Proc. Letters"},{"key":"15_CR6","doi-asserted-by":"publisher","first-page":"1777","DOI":"10.1016\/j.dam.2010.06.016","volume":"158","author":"N. Eggeman","year":"2010","unstructured":"Eggeman, N., Havet, F., Noble, S.: k-L(2, 1)-Labelling for Planar Graphs is NP-Complete for k\u2009\u2265\u20094. Disc. Appl. Math.\u00a0158, 1777\u20131788 (2010)","journal-title":"Disc. Appl. Math."},{"key":"15_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1007\/11523468_30","volume-title":"Automata, Languages and Programming","author":"J. Fiala","year":"2005","unstructured":"Fiala, J., Golovach, P., Kratochv\u00edl, J.: Distance Constrained Labelings of Graphs of Bounded Treewidth. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 360\u2013372. Springer, Heidelberg (2005)"},{"key":"15_CR8","doi-asserted-by":"publisher","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. Disc. Appl. Math.\u00a0113, 59\u201372 (2001)","journal-title":"Disc. Appl. Math."},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"1405","DOI":"10.1016\/j.disc.2007.07.075","volume":"308","author":"D. Gon\u00e7alves","year":"2008","unstructured":"Gon\u00e7alves, D.: On the L(p; 1)-labelling of graphs. Disc. Math.\u00a0308, 1405\u20131414 (2008)","journal-title":"Disc. Math."},{"key":"15_CR10","doi-asserted-by":"publisher","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. Disc. Math.\u00a05, 586\u2013595 (1992)","journal-title":"SIAM J. Disc. Math."},{"key":"15_CR11","doi-asserted-by":"publisher","first-page":"1497","DOI":"10.1109\/PROC.1980.11899","volume":"68","author":"W.K. Hale","year":"1980","unstructured":"Hale, W.K.: Frequency assignemnt: Theory and applications. Proc. IEEE\u00a068, 1497\u20131514 (1980)","journal-title":"Proc. IEEE"},{"key":"15_CR12","unstructured":"Havet, F., Reed, B., Sereni, J.-S.: L(2,1)-labellings of graphs. In: Proc. of SODA 2008, pp. 621\u2013630 (2008)"},{"key":"15_CR13","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/s00453-009-9302-7","volume":"59","author":"F. Havet","year":"2011","unstructured":"Havet, F., Klazar, M., Kratochv\u00edl, J., Kratsch, D., Liedloff, M.: Exact algorithms for L(2,1)-labeling of graphs. Algorithmica\u00a059, 169\u2013194 (2011)","journal-title":"Algorithmica"},{"key":"15_CR14","unstructured":"Havet, F., Klazar, M., Kratochv\u00edl, J., Kratsch, D., Liedloff, M.: Exact Algorithms for L(p,q)-labelings of graphs (manuscript)"},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"3270","DOI":"10.1016\/j.disc.2008.09.028","volume":"309","author":"R. Janczewski","year":"2009","unstructured":"Janczewski, R., Kosowski, A., Ma\u0142afiejski, M.: The complexity of the L(p,q)-labeling problem for bipartite planar graphs of small degree. Discrete Mathematics\u00a0309, 3270\u20133279 (2009)","journal-title":"Discrete Mathematics"},{"key":"15_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/978-3-642-20877-5_9","volume-title":"Theory and Applications of Models of Computation","author":"K. Junosza-Szaniawski","year":"2011","unstructured":"Junosza-Szaniawski, K., Kratochv\u00edl, J., Liedloff, M., Rossmanith, P., Rz\u0105\u017cewski, P.: Fast Exact Algorithm for L(2,1)-Labeling of Graphs. In: Ogihara, M., Tarui, J. (eds.) TAMC 2011. LNCS, vol.\u00a06648, pp. 82\u201393. Springer, Heidelberg (2011)"},{"key":"15_CR17","unstructured":"Junosza-Szaniawski, K., Rz\u0105\u017cewski, P.: Determining L(2,1)-span in Polynomial Space. arXiv:1104.4506v1 [cs.DM]"},{"key":"15_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/978-3-642-19222-7_4","volume-title":"Combinatorial Algorithms","author":"K. Junosza-Szaniawski","year":"2011","unstructured":"Junosza-Szaniawski, K., Rz\u0105\u017cewski, P.: On Improved Exact Algorithms for L(2,1)-Labeling of Graphs. In: Iliopoulos, C.S., Smyth, W.F. (eds.) IWOCA 2010. LNCS, vol.\u00a06460, pp. 34\u201337. Springer, Heidelberg (2011)"},{"key":"15_CR19","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1016\/j.ipl.2011.04.010","volume":"111","author":"K. Junosza-Szaniawski","year":"2011","unstructured":"Junosza-Szaniawski, K., Rz\u0105\u017cewski, P.: On the Complexity of Exact Algorithm for L(2,1)-labeling of Graphs. Inf. Proc. Letters\u00a0111, 697\u2013701 (2011)","journal-title":"Inf. Proc. Letters"},{"key":"15_CR20","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1016\/j.dam.2004.01.020","volume":"14","author":"D. Kr\u00e1l\u2019","year":"2005","unstructured":"Kr\u00e1l\u2019, D.: An exact algorithm for channel assignment problem. Discrete Applied Mathematics\u00a014, 326\u2013331 (2005)","journal-title":"Discrete Applied Mathematics"},{"key":"15_CR21","volume-title":"A problem of maximum consistent subsets. IBM Research Report RC-240","author":"R.E. Miller","year":"1960","unstructured":"Miller, R.E., Muller, D.E.: A problem of maximum consistent subsets. IBM Research Report RC-240. Thomas J. Watson Research Center, New York (1960)"},{"key":"15_CR22","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"J.W. Moon","year":"1965","unstructured":"Moon, J.W., Moser, L.: On cliques in graphs. Israel J. Math.\u00a03, 23\u201328 (1965)","journal-title":"Israel J. Math."},{"key":"15_CR23","first-page":"17","volume":"13","author":"D.R. Wood","year":"2011","unstructured":"Wood, D.R.: On the number of maximal independent sets in a graph. Disc. Math. and Theoretical Computer Science\u00a013, 17\u201320 (2011)","journal-title":"Disc. Math. and Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-34611-8_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T13:00:39Z","timestamp":1620133239000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-34611-8_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642346101","9783642346118"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-34611-8_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}