{"id":13232,"date":"2021-12-07T21:06:11","date_gmt":"2021-12-08T02:06:11","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=13232"},"modified":"2021-12-07T21:06:11","modified_gmt":"2021-12-08T02:06:11","slug":"tr-07-23-local-ptas-for-independent-set-and-vertex-cover-in-location-aware-unit-disk-graphs","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-23-local-ptas-for-independent-set-and-vertex-cover-in-location-aware-unit-disk-graphs\/","title":{"rendered":"TR-07-23: Local PTAS for Independent Set and Vertex Cover in Location Aware Unit Disk Graphs"},"content":{"rendered":"

Carleton University
\nTechnical Report<\/a> TR-07-23
\nDecember 12, 2007<\/p>\n

Local PTAS for Independent Set and Vertex Cover in Location Aware Unit Disk Graphs<\/h2>\n
\n
\n
\n
\n
\n
\n
\n
\n

Andreas Wiese & Evangelos Kranakis<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n

\n

Abstract<\/h3>\n

We present the \ufb01rst local approximation schemes for maximum independent set and minimum vertex cover in unit disk graphs. In the graph model we assume that each node knows its geographic coordinates in the plane (location aware nodes). Our algorithms are local in the sense that the status of each node v (whether or not v is in the computed set) depends only on the vertices which are a constant number of hops away from v. This constant is independent of the size of the network. We give upper bounds for the constant depending on the desired approximation ratio. We show that the processing time which is necessary in order to compute the status of a single vertex is bounded by a polynomial in the number of vertices which are at most a constant number of vertices away from it. Our algorithms give the best possible approximation ratios for this setting.The technique which we use to obtain the algorithm for vertex cover can also be employed for constructing the \ufb01rst global PTAS for this problem in unit disk graph which does not need the embedding of the graph as part of the input.<\/p>\n

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

Carleton University Technical Report TR-07-23 December 12, 2007 Local PTAS for Independent Set and Vertex Cover in Location Aware Unit Disk Graphs Andreas Wiese & Evangelos Kranakis Abstract We present the \ufb01rst local approximation schemes for maximum independent set and minimum vertex cover in unit disk graphs. In the graph model we assume that each […]<\/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-23: Local PTAS for Independent Set and Vertex Cover in Location Aware Unit Disk Graphs - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-07-23 December 12, 2007 Local PTAS for Independent Set and Vertex Cover in Location Aware Unit Disk Graphs Andreas\" \/>\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-23-local-ptas-for-independent-set-and-vertex-cover-in-location-aware-unit-disk-graphs\/\" \/>\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-23-local-ptas-for-independent-set-and-vertex-cover-in-location-aware-unit-disk-graphs\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-23-local-ptas-for-independent-set-and-vertex-cover-in-location-aware-unit-disk-graphs\/\",\"name\":\"TR-07-23: Local PTAS for Independent Set and Vertex Cover in Location Aware Unit Disk Graphs - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-12-08T02:06:11+00:00\",\"dateModified\":\"2021-12-08T02:06:11+00:00\",\"description\":\"Carleton University Technical Report TR-07-23 December 12, 2007 Local PTAS for Independent Set and Vertex Cover in Location Aware Unit Disk Graphs Andreas\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-23-local-ptas-for-independent-set-and-vertex-cover-in-location-aware-unit-disk-graphs\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-23-local-ptas-for-independent-set-and-vertex-cover-in-location-aware-unit-disk-graphs\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-23-local-ptas-for-independent-set-and-vertex-cover-in-location-aware-unit-disk-graphs\/#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-23: Local PTAS for Independent Set and Vertex Cover in Location Aware Unit Disk Graphs\"}]},{\"@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-23: Local PTAS for Independent Set and Vertex Cover in Location Aware Unit Disk Graphs - School of Computer Science","description":"Carleton University Technical Report TR-07-23 December 12, 2007 Local PTAS for Independent Set and Vertex Cover in Location Aware Unit Disk Graphs Andreas","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-23-local-ptas-for-independent-set-and-vertex-cover-in-location-aware-unit-disk-graphs\/","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-23-local-ptas-for-independent-set-and-vertex-cover-in-location-aware-unit-disk-graphs\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-23-local-ptas-for-independent-set-and-vertex-cover-in-location-aware-unit-disk-graphs\/","name":"TR-07-23: Local PTAS for Independent Set and Vertex Cover in Location Aware Unit Disk Graphs - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-12-08T02:06:11+00:00","dateModified":"2021-12-08T02:06:11+00:00","description":"Carleton University Technical Report TR-07-23 December 12, 2007 Local PTAS for Independent Set and Vertex Cover in Location Aware Unit Disk Graphs Andreas","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-23-local-ptas-for-independent-set-and-vertex-cover-in-location-aware-unit-disk-graphs\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-23-local-ptas-for-independent-set-and-vertex-cover-in-location-aware-unit-disk-graphs\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-23-local-ptas-for-independent-set-and-vertex-cover-in-location-aware-unit-disk-graphs\/#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-23: Local PTAS for Independent Set and Vertex Cover in Location Aware Unit Disk Graphs"}]},{"@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\/13232"}],"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=13232"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13232\/revisions"}],"predecessor-version":[{"id":13233,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13232\/revisions\/13233"}],"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=13232"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}