{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T14:38:14Z","timestamp":1648564694384},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2016,3]]},"abstract":"<jats:p> Let [Formula: see text] be a graph with a positive integer weight [Formula: see text] for each vertex [Formula: see text]. One wishes to assign each edge [Formula: see text] of [Formula: see text] a positive integer [Formula: see text] as a color so that [Formula: see text] for any vertex [Formula: see text] and any two edges [Formula: see text] and [Formula: see text] incident to [Formula: see text]. Such an assignment [Formula: see text] is called an [Formula: see text]-edge-coloring of [Formula: see text], and the maximum integer assigned to edges is called the span of [Formula: see text]. The [Formula: see text]-chromatic index of [Formula: see text] is the minimum span over all [Formula: see text]-edge-colorings of [Formula: see text]. In the paper, we present various upper and lower bounds on the [Formula: see text]-chromatic index, and obtain three efficient algorithms to find an [Formula: see text]-edge-coloring of a given graph. One of them finds an [Formula: see text]-edge-coloring with span smaller than twice the [Formula: see text]-chromatic index. <\/jats:p>","DOI":"10.1142\/s1793830916500154","type":"journal-article","created":{"date-parts":[[2015,12,15]],"date-time":"2015-12-15T02:34:52Z","timestamp":1450146892000},"page":"1650015","source":"Crossref","is-referenced-by-count":0,"title":["Generalized edge-colorings of weighted graphs"],"prefix":"10.1142","volume":"08","author":[{"given":"Yuji","family":"Obata","sequence":"first","affiliation":[{"name":"Department of Informatics, Kwansei Gakuin University, 2-1 Gakuen, Sanda 669-1337, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takao","family":"Nishizeki","sequence":"additional","affiliation":[{"name":"Department of Informatics, Kwansei Gakuin University, 2-1 Gakuen, Sanda 669-1337, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2016,2,26]]},"reference":[{"key":"S1793830916500154BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170002"},{"key":"S1793830916500154BIB002","volume-title":"Introduction to Algorithms","author":"Corman T. H.","year":"2001"},{"key":"S1793830916500154BIB004","doi-asserted-by":"publisher","DOI":"10.1137\/0210055"},{"key":"S1793830916500154BIB005","volume-title":"Graph Coloring Problems","author":"Jensen T. R.","year":"1995"},{"key":"S1793830916500154BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90026-5"},{"key":"S1793830916500154BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(02)00821-X"},{"key":"S1793830916500154BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(03)00236-X"},{"key":"S1793830916500154BIB009","doi-asserted-by":"publisher","DOI":"10.4036\/iis.1994.19"},{"key":"S1793830916500154BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.02.015"},{"key":"S1793830916500154BIB012","volume-title":"Scheduling: Theory, Algorithms and Systems","author":"Pinedo M. L.","year":"2008"},{"key":"S1793830916500154BIB013","doi-asserted-by":"publisher","DOI":"10.1002\/sapm1949281148"},{"key":"S1793830916500154BIB014","volume-title":"Graph Edge Coloring","author":"Stiebitz M.","year":"2012"},{"key":"S1793830916500154BIB015","volume-title":"Introduction to Graph Theory","author":"West D. B.","year":"1996"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830916500154","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:02:43Z","timestamp":1565121763000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830916500154"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,26]]},"references-count":13,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2016,2,26]]},"published-print":{"date-parts":[[2016,3]]}},"alternative-id":["10.1142\/S1793830916500154"],"URL":"https:\/\/doi.org\/10.1142\/s1793830916500154","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,26]]}}}