{"id":13186,"date":"2021-12-07T20:30:02","date_gmt":"2021-12-08T01:30:02","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=13186"},"modified":"2021-12-07T20:30:02","modified_gmt":"2021-12-08T01:30:02","slug":"tr-07-01-location-oblivious-distributed-unit-disk-graph-coloring","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-01-location-oblivious-distributed-unit-disk-graph-coloring\/","title":{"rendered":"TR-07-01: Location Oblivious Distributed Unit Disk Graph Coloring"},"content":{"rendered":"

Carleton University
\nTechnical Report<\/a> TR-07-01
\nJanuary 26, 2007<\/p>\n

Location Oblivious Distributed Unit Disk Graph Coloring<\/h2>\n
\n
\n
\n
\n
\n
\n
\n
\n
\n

Mathieu Couture, Michel Barbeau, Prosenjit Bose, Paz Carmi, Evangelos Kranakis<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n

\n

Abstract<\/h3>\n

We present the first location oblivious distributed unit disk graph coloring algorithm having a provable performance ratio of three (i.e. the number of colors used by the algorithm is at most three times the chromatic number of the graph). This is an improvement over the standard sequential coloring algorithm since we present a new lower bound of 10\/3 for the worst-case performance ratio of the sequential coloring algorithm. The previous greatest lower bound on the performance ratio of the sequential coloring algorithm was 5\/2. Using simulation, we also compare our algorithm with other existing unit disk graph coloring algorithms.<\/p>\n

TR-07-01.pdf<\/a><\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

Carleton University Technical Report TR-07-01 January 26, 2007 Location Oblivious Distributed Unit Disk Graph Coloring Mathieu Couture, Michel Barbeau, Prosenjit Bose, Paz Carmi, Evangelos Kranakis Abstract We present the first location oblivious distributed unit disk graph coloring algorithm having a provable performance ratio of three (i.e. the number of colors used by the algorithm is […]<\/p>\n","protected":false},"author":49,"featured_media":0,"parent":12385,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_relevanssi_hide_post":"","_relevanssi_hide_content":"","_relevanssi_pin_for_all":"","_relevanssi_pin_keywords":"","_relevanssi_unpin_keywords":"","_relevanssi_related_keywords":"","_relevanssi_related_include_ids":"","_relevanssi_related_exclude_ids":"","_relevanssi_related_no_append":"","_relevanssi_related_not_related":"","_relevanssi_related_posts":"","_relevanssi_noindex_reason":"","_mi_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":"","_links_to":"","_links_to_target":""},"yoast_head":"\nTR-07-01: Location Oblivious Distributed Unit Disk Graph Coloring - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-07-01 January 26, 2007 Location Oblivious Distributed Unit Disk Graph Coloring Mathieu Couture, Michel Barbeau,\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-01-location-oblivious-distributed-unit-disk-graph-coloring\/\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-01-location-oblivious-distributed-unit-disk-graph-coloring\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-01-location-oblivious-distributed-unit-disk-graph-coloring\/\",\"name\":\"TR-07-01: Location Oblivious Distributed Unit Disk Graph Coloring - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-12-08T01:30:02+00:00\",\"dateModified\":\"2021-12-08T01:30:02+00:00\",\"description\":\"Carleton University Technical Report TR-07-01 January 26, 2007 Location Oblivious Distributed Unit Disk Graph Coloring Mathieu Couture, Michel Barbeau,\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-01-location-oblivious-distributed-unit-disk-graph-coloring\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-01-location-oblivious-distributed-unit-disk-graph-coloring\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-01-location-oblivious-distributed-unit-disk-graph-coloring\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/carleton.ca\/scs\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Research\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"SCS Technical Reports\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"Technical Reports 2007\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-07-01: Location Oblivious Distributed Unit Disk Graph Coloring\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/carleton.ca\/scs\/#website\",\"url\":\"https:\/\/carleton.ca\/scs\/\",\"name\":\"School of Computer Science\",\"description\":\"Carleton University\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/carleton.ca\/scs\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"TR-07-01: Location Oblivious Distributed Unit Disk Graph Coloring - School of Computer Science","description":"Carleton University Technical Report TR-07-01 January 26, 2007 Location Oblivious Distributed Unit Disk Graph Coloring Mathieu Couture, Michel Barbeau,","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-01-location-oblivious-distributed-unit-disk-graph-coloring\/","twitter_misc":{"Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-01-location-oblivious-distributed-unit-disk-graph-coloring\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-01-location-oblivious-distributed-unit-disk-graph-coloring\/","name":"TR-07-01: Location Oblivious Distributed Unit Disk Graph Coloring - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-12-08T01:30:02+00:00","dateModified":"2021-12-08T01:30:02+00:00","description":"Carleton University Technical Report TR-07-01 January 26, 2007 Location Oblivious Distributed Unit Disk Graph Coloring Mathieu Couture, Michel Barbeau,","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-01-location-oblivious-distributed-unit-disk-graph-coloring\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-01-location-oblivious-distributed-unit-disk-graph-coloring\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-01-location-oblivious-distributed-unit-disk-graph-coloring\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/carleton.ca\/scs\/"},{"@type":"ListItem","position":2,"name":"Research","item":"https:\/\/carleton.ca\/scs\/research\/"},{"@type":"ListItem","position":3,"name":"SCS Technical Reports","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/"},{"@type":"ListItem","position":4,"name":"Technical Reports 2007","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/"},{"@type":"ListItem","position":5,"name":"TR-07-01: Location Oblivious Distributed Unit Disk Graph Coloring"}]},{"@type":"WebSite","@id":"https:\/\/carleton.ca\/scs\/#website","url":"https:\/\/carleton.ca\/scs\/","name":"School of Computer Science","description":"Carleton University","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/carleton.ca\/scs\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"}]}},"acf":{"banner_image_type":"none","banner_button":"no"},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13186"}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/49"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=13186"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13186\/revisions"}],"predecessor-version":[{"id":13187,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13186\/revisions\/13187"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12385"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=13186"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}