{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:26:18Z","timestamp":1759638378138},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,1,4]],"date-time":"2007-01-04T00:00:00Z","timestamp":1167868800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2007,1,4]],"date-time":"2007-01-04T00:00:00Z","timestamp":1167868800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2007,7]]},"DOI":"10.1007\/s10878-006-9034-4","type":"journal-article","created":{"date-parts":[[2007,1,3]],"date-time":"2007-01-03T19:59:11Z","timestamp":1167854351000},"page":"63-86","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Packing [1, \u0394]-factors in graphs of small degree"],"prefix":"10.1007","volume":"14","author":[{"given":"Adrian","family":"Kosowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Ma\u0142afiejski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"\u017byli\u0144ski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,1,4]]},"reference":[{"key":"9034_CR1","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1002\/jgt.3190080404","volume":"8","author":"Y Caro","year":"1984","unstructured":"Caro Y (1984) The decomposition of trees into subtrees. J Graph Theor 8:471\u2013479","journal-title":"J Graph Theor"},{"key":"9034_CR2","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/3-540-46648-7_35","volume":"1731","author":"N Castro","year":"1999","unstructured":"de Castro N, Cobos FJ, Dana JC, Marquez A, Noy M (1999) Triangle-free planar graphs as segment intersection graphs. Lecture Notes Comp Sci 1731:341\u2013358","journal-title":"Lecture Notes Comp Sci"},{"key":"9034_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/147508.147511","volume":"39","author":"B Chazelle","year":"1992","unstructured":"Chazelle B, Edelsbrunner H (1992) An optimal algorithm for intersecting line segments in the plane. J ACM 39:1\u201354","journal-title":"J ACM"},{"key":"9034_CR4","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0012-365X(88)90193-8","volume":"72","author":"CJ Colbourn","year":"1988","unstructured":"Colbourn CJ (1988) Edge-packing of graphs and network ealiability. Disc Math 72:49\u201361","journal-title":"Disc Math"},{"key":"9034_CR5","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0020-0190(98)00046-5","volume":"66","author":"J Czyzowicz","year":"1998","unstructured":"Czyzowicz J, Kranakis E, Urrutia J (1998) A simple proof of the representation of bipartite planar graphs as the contact graphs of orthogonal straight line segments. Inform Proc Lett 66:125\u2013126","journal-title":"Inform Proc Lett"},{"key":"9034_CR6","unstructured":"Dangelmayr C (2004) Intersection graphs of straight-line segments. In: 4th Annual CGC Workshop on Computational Geometry (Stels)"},{"issue":"1","key":"9034_CR7","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/0196-6774(86)90002-7","volume":"7","author":"ME Dyer","year":"1986","unstructured":"Dyer ME, Frieze AM (1986) Planar 3DM is NP-complete. J Algorith 7(1):174\u2013184","journal-title":"J Algorith"},{"issue":"2","key":"9034_CR8","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1007\/s00453-002-0992-3","volume":"35","author":"LM Favrholdt","year":"2003","unstructured":"Favrholdt LM, Nielsen MN (2003) On-line edge-coloring with a fixed number of colors. Algorithmica 35(2):176\u2013191","journal-title":"Algorithmica"},{"key":"9034_CR9","doi-asserted-by":"crossref","unstructured":"Finke U, Hinchirs K (1995) Overlaying simply connected planar subdivisions in linear time. In: Proc ACM SoCG, pp 119\u2013126","DOI":"10.1145\/220279.220292"},{"key":"9034_CR10","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1007\/3-540-45753-4_11","volume":"2462","author":"U Feige","year":"2002","unstructured":"Feige U, Ofek E, Wieder U (2002) Approximating maximum edge coloring in multigraphs. Lecture Notes Comp Sci 2462:108\u2013121","journal-title":"Lecture Notes Comp Sci"},{"key":"9034_CR11","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: A guide to the theory of NP-completeness. Freeman, New York"},{"key":"9034_CR12","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0012-365X(91)90069-E","volume":"87","author":"IB-A Hartman","year":"1991","unstructured":"Hartman IB-A, Newman I, Ziv R (1991) On grid intersection graphs. Disc Math 87:41\u201352","journal-title":"Disc Math"},{"key":"9034_CR13","unstructured":"Hartvigsen D (1984) Extensions of matching theory, PhD Thesis. Carnegie-Mellon University"},{"issue":"1\u20133","key":"9034_CR14","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/S0166-218X(97)00083-8","volume":"81","author":"LS Heath","year":"1998","unstructured":"Heath LS, Vergara JPC (1998) Edge-packing planar graphs by cyclic graphs. Disc Appl Math 81(1\u20133):169\u2013180","journal-title":"Disc Appl Math"},{"key":"9034_CR15","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer I (1981) The NP-completeness of edge-colouring. SIAM J Comp 10:718\u2013720","journal-title":"SIAM J Comp"},{"key":"9034_CR16","doi-asserted-by":"crossref","first-page":"113","DOI":"10.7151\/dmgt.1162","volume":"22","author":"J Ivanco","year":"2002","unstructured":"Ivanco J, Meszka M, Skupie\u0144 Z (2002) Decompositions of multigraphs into parts with two edges. Discuss Math Graph Theor 22:113\u2013121","journal-title":"Discuss Math Graph Theor"},{"issue":"2","key":"9034_CR17","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1006\/jagm.2000.1121","volume":"37","author":"DP Jacobs","year":"2000","unstructured":"Jacobs DP, Jamison RE (2000) Complexity of recognizing equal unions in families of sets. J Algor 37(2):495\u2013504","journal-title":"J Algor"},{"key":"9034_CR18","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1002\/jgt.3190090416","volume":"9","author":"M J\u00fcnger","year":"1985","unstructured":"J\u00fcnger M, Reinelt G, Pulleyblank WR (1985) On partitioning the edges of graphs into connected subgraphs. J Graph Theor 9:539\u2013549","journal-title":"J Graph Theor"},{"key":"9034_CR19","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1002\/jgt.10022","volume":"39","author":"K Kawarabayashi","year":"2002","unstructured":"Kawarabayashi K, Matsuda H, Oda Y, Ota K (2002) Path factors in cubic graphs. J Graph Theor 39:188\u2013193","journal-title":"J Graph Theor"},{"key":"9034_CR20","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/BF01456961","volume":"77","author":"D K\u00f6nig","year":"1916","unstructured":"K\u00f6nig D (1916) Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math Ann 77:453\u2013465","journal-title":"Math Ann"},{"key":"9034_CR21","unstructured":"Kosowski A, Ma\u0142afiejski M, \u017byli\u0144ski P (in press) Cooperative mobile guards in grids, to appear in Computational Geometry: Theory and Applications"},{"key":"9034_CR22","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/11751540_18","volume":"3980","author":"A Kosowski","year":"2006","unstructured":"Kosowski A, Ma\u0142afiejski M, \u017byli\u0144ski P (2006) Fault tolerant guarding of grids. Lecture Notes Comp Sci 3980:161\u2013170","journal-title":"Lecture Notes Comp Sci"},{"issue":"1","key":"9034_CR23","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0196-6774(83)90032-9","volume":"4","author":"D Leven","year":"1983","unstructured":"Leven D, Galil Z (1983) NP-completeness of finding the chromatic index of regular graphs. J Algorith 4(1):35\u201344","journal-title":"J Algorith"},{"key":"9034_CR24","unstructured":"Liaw BC, Huang NF, Lee RCT (1993) The minimum cooperative guards problem on k-spiral polygons. In: Proc CCCG, pp 97\u2013101"},{"key":"9034_CR25","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0020-0190(94)00128-6","volume":"52","author":"BC Liaw","year":"1994","unstructured":"Liaw BC, Lee RCT (1994) An optimal algorithm to solve the minimum weakly cooperative guards problem for 1-spiral polygons. Inf Process Lett 52:69\u201375","journal-title":"Inf Process Lett"},{"key":"9034_CR26","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1007\/s00373-004-0581-0","volume":"20","author":"Z Lonc","year":"2004","unstructured":"Lonc Z, Meszka M, Skupie\u0144 Z (2004) Edge decompositions of multigraphs into 3-matchings. Graphs Comb 20:507\u2013515","journal-title":"Graphs Comb"},{"key":"9034_CR27","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1007\/11424758_68","volume":"3480","author":"M Ma\u0142afiejski","year":"2005","unstructured":"Ma\u0142afiejski M, \u017byli\u0144ski P (2005) Weakly cooperative guards in grids. Lecture Notes Comp Sci 3480:647\u2013656","journal-title":"Lecture Notes Comp Sci"},{"key":"9034_CR28","unstructured":"Nierhoff T, \u017byli\u0144ski P (2003) Cooperative guards in grids. In: 3rd Annual CGC Workshop on Computational Geometry, Neustrelitz"},{"key":"9034_CR29","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0020-0190(86)90050-5","volume":"23","author":"S Ntafos","year":"1986","unstructured":"Ntafos S (1986) On gallery watchmen in grids. Inf Proc Lett 23:99\u2013102","journal-title":"Inf Proc Lett"},{"key":"9034_CR30","unstructured":"O\u2019Rourke J (1987) Art gallery theorems and algorithms. Oxford University Press"},{"key":"9034_CR31","unstructured":"Scheinerman ER (1984) Intersection classes and multiple intersection parameters of graphs. PhD thesis, Princenton University"},{"key":"9034_CR32","volume-title":"Combinatorial optimization: polyhedra and efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver A (2003) Combinatorial optimization: polyhedra and efficiency. Springer, Berlin Heidelberg New York"},{"key":"9034_CR33","volume-title":"Art gallery and illumination problems. Handbook on computational geometry","author":"J Urrutia","year":"2000","unstructured":"Urrutia J (2000) Art gallery and illumination problems. Handbook on computational geometry, Elsevier Science, Amsterdam"},{"issue":"1\u20133","key":"9034_CR34","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/S0012-365X(03)00296-6","volume":"276","author":"M Wo\u017aniak","year":"2004","unstructured":"Wo\u017aniak M (2004) Packing of graphs and permutations\u2014a survey. Disc Math 276(1\u20133):379\u2013391","journal-title":"Disc Math"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-006-9034-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-006-9034-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-006-9034-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-006-9034-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,17]],"date-time":"2022-05-17T22:27:25Z","timestamp":1652826445000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-006-9034-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1,4]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,7]]}},"alternative-id":["9034"],"URL":"https:\/\/doi.org\/10.1007\/s10878-006-9034-4","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1,4]]},"assertion":[{"value":"4 January 2007","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}