{"id":157281,"date":"2008-09-01T00:00:00","date_gmt":"2008-09-01T00:00:00","guid":{"rendered":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/msr-research-item\/edge-coloring-and-decompositions-of-weighted-graphs\/"},"modified":"2018-10-16T21:51:46","modified_gmt":"2018-10-17T04:51:46","slug":"edge-coloring-and-decompositions-of-weighted-graphs","status":"publish","type":"msr-research-item","link":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/publication\/edge-coloring-and-decompositions-of-weighted-graphs\/","title":{"rendered":"Edge Coloring and Decompositions of Weighted Graphs"},"content":{"rendered":"

We consider two generalizations of the edge coloring problem in bipartite graphs. The first problem we consider is the weighted bipartite edge coloring<\/span> problem where we are given an edge-weighted bipartite graph G<\/em>\u2009=\u2009(V<\/em>,E<\/em>) with weights w<\/em>:E<\/em>\u2192[0,1]. The task is to find a proper weighted coloring<\/em> of the edges with as few colors as possible. An edge coloring of the weighted graph is called a proper weighted coloring<\/em> if the sum of the weights of the edges incident to a vertex of any color is at most one. We give a polynomial time algorithm for the weighted bipartite edge coloring<\/span> problem which returns a proper weighted coloring using at most \u23082.25 n<\/em>\u2309 colors where n<\/em> is the maximum total weight incident at any vertex. This improves on the previous best bound of Correa and Goemans\u00a0[5] which returned a coloring using 2.557n<\/em>\u2009+\u2009o<\/em>(n<\/em>) colors. The second problem we consider is the Balanced Decomposition of Bipartite graphs<\/span> problem where we are given a bipartite graph G<\/em>\u2009=\u2009(V<\/em>,E<\/em>) and \u03b1<\/em> 1<\/sub>,…,\u03b1<\/em> k<\/em> <\/sub>\u2009\u2208\u2009(0,1) summing to one. The task is to find a partition E<\/em> 1<\/sub>,…, E<\/em> k<\/em> <\/sub> of E<\/em> such that d<\/mi>e<\/mi>g<\/mi>E<\/mi>i<\/mi><\/msub><\/mrow><\/msub>(<\/mo>v<\/mi>)<\/mo><\/math>\">d<\/span>e<\/span>g<\/span>E<\/span>i<\/span><\/span><\/span><\/span><\/span>(<\/span>v<\/span>)<\/span><\/span><\/span><\/span><\/span><\/span> is close to \u03b1<\/em> i<\/em> <\/sub> deg<\/em> E<\/em> <\/sub>(v<\/em>) for each 1\u2009\u2264\u2009i<\/em>\u2009\u2264\u2009k<\/em> and v<\/em>\u2009\u2208\u2009V<\/em>. We give an alternate proof of the result of Correa and Goemans\u00a0[5] that there is a decomposition such that ⌊<\/mo>α<\/mi>i<\/mi><\/msub>d<\/mi>e<\/mi>g<\/mi>E<\/mi><\/msub>(<\/mo>v<\/mi>)<\/mo>⌋<\/mo>−<\/mo>2<\/mn>≤<\/mo>d<\/mi>e<\/mi>g<\/mi>E<\/mi>i<\/mi><\/msub><\/mrow><\/msub>(<\/mo>v<\/mi>)<\/mo>≤<\/mo>⌈<\/mo>α<\/mi>i<\/mi><\/msub>d<\/mi>e<\/mi>g<\/mi>E<\/mi><\/msub>(<\/mo>v<\/mi>)<\/mo>⌉<\/mo>+<\/mo>2<\/mn><\/math>\">\u230a<\/span>\u03b1<\/span>i<\/span><\/span>d<\/span>e<\/span>g<\/span>E<\/span><\/span>(<\/span>v<\/span>)<\/span>\u230b<\/span>\u2212<\/span>2<\/span>\u2264<\/span>d<\/span>e<\/span>g<\/span>E<\/span>i<\/span><\/span><\/span><\/span><\/span>(<\/span>v<\/span>)<\/span>\u2264<\/span>\u2308<\/span>\u03b1<\/span>i<\/span><\/span>d<\/span>e<\/span>g<\/span>E<\/span><\/span>(<\/span>v<\/span>)<\/span>\u2309<\/span>+<\/span>2<\/span><\/span><\/span><\/span><\/span><\/span> for each v<\/em>\u2009\u2208\u2009V<\/em> and 1\u2009\u2264\u2009i<\/em>\u2009\u2264\u2009k<\/em>. Moreover, we show that the additive error can be improved from two to one if only upper bounds or only lower bounds on the degree are present. All our results hold also for bipartite multigraphs, and the decomposition results hold also for general graphs.<\/p>\n","protected":false},"excerpt":{"rendered":"

We consider two generalizations of the edge coloring problem in bipartite graphs. The first problem we consider is the weighted bipartite edge coloring problem where we are given an edge-weighted bipartite graph G\u2009=\u2009(V,E) with weights w:E\u2192[0,1]. The task is to find a proper weighted coloring of the edges with as few colors as possible. An […]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":null,"msr_publishername":"Springer","msr_publisher_other":"","msr_booktitle":"","msr_chapter":"","msr_edition":"Algorithms - ESA 2008, 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008. Proceedings","msr_editors":"","msr_how_published":"","msr_isbn":"978-3-540-87743-1","msr_issue":"","msr_journal":"","msr_number":"","msr_organization":"","msr_pages_string":"405\u2013416","msr_page_range_start":"405","msr_page_range_end":"416","msr_series":"Lecture Notes in Computer Science","msr_volume":"5193","msr_copyright":"","msr_conference_name":"Algorithms - ESA 2008, 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008. Proceedings","msr_doi":"","msr_arxiv_id":"","msr_s2_paper_id":"","msr_mag_id":"","msr_pubmed_id":"","msr_other_authors":"","msr_other_contributors":"","msr_speaker":"","msr_award":"","msr_affiliation":"","msr_institution":"","msr_host":"","msr_version":"","msr_duration":"","msr_original_fields_of_study":"","msr_release_tracker_id":"","msr_s2_match_type":"","msr_citation_count_updated":"","msr_published_date":"2008-09-01","msr_highlight_text":"","msr_notes":"","msr_longbiography":"","msr_publicationurl":"http:\/\/dx.doi.org\/10.1007\/978-3-540-87744-8_34","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"","msr_journal_url":"","msr_s2_pdf_url":"","msr_year":2008,"msr_citation_count":0,"msr_influential_citations":0,"msr_reference_count":0,"msr_s2_match_confidence":0,"msr_microsoftintellectualproperty":true,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[],"msr_hide_image_in_river":0,"footnotes":""},"msr-research-highlight":[],"research-area":[13561],"msr-publication-type":[193716],"msr-publisher":[],"msr-focus-area":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-157281","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-algorithms","msr-locale-en_us"],"msr_publishername":"Springer","msr_edition":"Algorithms - ESA 2008, 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008. Proceedings","msr_affiliation":"","msr_published_date":"2008-09-01","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"405\u2013416","msr_chapter":"","msr_isbn":"978-3-540-87743-1","msr_journal":"","msr_volume":"5193","msr_number":"","msr_editors":"","msr_series":"Lecture Notes in Computer Science","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"224995","msr_publicationurl":"http:\/\/dx.doi.org\/10.1007\/978-3-540-87744-8_34","msr_doi":"","msr_publication_uploader":[{"type":"file","title":"edgecoloring.pdf","viewUrl":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-content\/uploads\/2008\/09\/edgecoloring.pdf","id":224995,"label_id":0},{"type":"url","title":"http:\/\/dx.doi.org\/10.1007\/978-3-540-87744-8_34","viewUrl":false,"id":false,"label_id":0}],"msr_related_uploader":"","msr_citation_count":0,"msr_citation_count_updated":"","msr_s2_paper_id":"","msr_influential_citations":0,"msr_reference_count":0,"msr_arxiv_id":"","msr_s2_author_ids":[],"msr_s2_open_access":false,"msr_s2_pdf_url":null,"msr_attachments":[{"id":0,"url":"http:\/\/dx.doi.org\/10.1007\/978-3-540-87744-8_34"},{"id":224995,"url":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-content\/uploads\/2008\/09\/edgecoloring.pdf"}],"msr-author-ordering":[{"type":"text","value":"Uriel Feige","user_id":0,"rest_url":false},{"type":"user_nicename","value":"mohsingh","user_id":32990,"rest_url":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=mohsingh"}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[],"msr_project":[],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"inproceedings","related_content":[],"_links":{"self":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/157281","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":2,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/157281\/revisions"}],"predecessor-version":[{"id":539700,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/157281\/revisions\/539700"}],"wp:attachment":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/media?parent=157281"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=157281"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=157281"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=157281"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=157281"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=157281"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=157281"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=157281"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=157281"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=157281"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=157281"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=157281"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=157281"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}