Localized Spanners for Wireless Networks.

We present a new efficient localized algorithm to construct, for any given quasi-unit disk graph G = (V,E) and any " > 0, a (1+ ")- spanner for G of maximum degree O(1) and total weight O(!(MST)), where !(MST) denotes the weight of a minimum spanning tree for V .We further show that similar localized techniques can be used to construct, for a given unit disk graph G = (V,E), a planar Cdel(1+")(1+π 2 )-spanner for G of maximum degree O(1) and total weight O(!(MST)). Here Cdel denotes the stretch factor of the unit Delaunay triangulation for V . Both constructions can be completed in O(1) communication rounds, and require each node to know its own coordinates.

Main Author: Damian, Mirela.
Other Authors: Pemmaraju, Sriram V.
Format: Villanova Faculty Authorship
Language: English
Published: 2010
Online Access: http://ezproxy.villanova.edu/login?url=https://digital.library.villanova.edu/Item/vudl:175689
PID vudl:175689
id vudl:175689
modeltype_str_mv vudl-system:CoreModel
vudl-system:CollectionModel
vudl-system:ResourceCollection
datastream_str_mv DC
PARENT-QUERY
PARENT-LIST-RAW
PARENT-LIST
MEMBER-QUERY
MEMBER-LIST-RAW
LEGACY-METS
LICENSE
AGENTS
PROCESS-MD
THUMBNAIL
STRUCTMAP
RELS-EXT
hierarchytype
sequence_vudl_175631_str 0000000020
has_order_str no
hierarchy_top_id vudl:641262
hierarchy_top_title Villanova faculty author
hierarchy_parent_id vudl:175631
hierarchy_parent_title Damian Mirela
hierarchy_sequence 0000000020
hierarchy_first_parent_id_str vudl:175689
hierarchy_sequence_sort_str 0000000020
hierarchy_all_parents_str_mv vudl:641262
vudl:172968
vudl:175631
first_indexed 2014-01-11T23:30:08Z
last_indexed 2021-04-12T19:01:13Z
recordtype vudl
fullrecord <root> <url> http://digital.library.villanova.edu/files/vudl:175689/DC </url> <thumbnail> http://digital.library.villanova.edu/files/vudl:175689/THUMBNAIL </thumbnail> </root>
spelling
institution Villanova University
collection Digital Library
language English
dc_source_str_mv Ad Hoc and Sensor Wireless Networks 9(3-4), Apri 2010, 305-328.
author Damian, Mirela.
author_facet_str_mv Damian, Mirela.
Pemmaraju, Sriram V.
author_or_contributor_facet_str_mv Damian, Mirela.
Pemmaraju, Sriram V.
author_s Damian, Mirela.
spellingShingle Damian, Mirela.
Localized Spanners for Wireless Networks.
author-letter Damian, Mirela.
author_sort_str Damian, Mirela.
author2 Pemmaraju, Sriram V.
author2Str Pemmaraju, Sriram V.
dc_title_str Localized Spanners for Wireless Networks.
title Localized Spanners for Wireless Networks.
title_short Localized Spanners for Wireless Networks.
title_full Localized Spanners for Wireless Networks.
title_fullStr Localized Spanners for Wireless Networks.
title_full_unstemmed Localized Spanners for Wireless Networks.
collection_title_sort_str localized spanners for wireless networks.
title_sort localized spanners for wireless networks.
format Villanova Faculty Authorship
description We present a new efficient localized algorithm to construct, for any given quasi-unit disk graph G = (V,E) and any " > 0, a (1+ ")- spanner for G of maximum degree O(1) and total weight O(!(MST)), where !(MST) denotes the weight of a minimum spanning tree for V .We further show that similar localized techniques can be used to construct, for a given unit disk graph G = (V,E), a planar Cdel(1+")(1+π 2 )-spanner for G of maximum degree O(1) and total weight O(!(MST)). Here Cdel denotes the stretch factor of the unit Delaunay triangulation for V . Both constructions can be completed in O(1) communication rounds, and require each node to know its own coordinates.
publishDate 2010
normalized_sort_date 2010-01-01T00:00:00Z
dc_date_str 2010
license_str protected
REPOSITORYNAME FgsRepos
REPOSBASEURL http://hades.library.villanova.edu:8088/fedora
fgs.state Active
fgs.label Localized Spanners for Wireless Networks.
fgs.ownerId diglibEditor
fgs.createdDate 2013-01-22T04:55:26.414Z
fgs.lastModifiedDate 2021-04-12T18:59:23.026Z
dc.title Localized Spanners for Wireless Networks.
dc.creator Damian, Mirela.
Pemmaraju, Sriram V.
dc.description We present a new efficient localized algorithm to construct, for any given quasi-unit disk graph G = (V,E) and any " > 0, a (1+ ")- spanner for G of maximum degree O(1) and total weight O(!(MST)), where !(MST) denotes the weight of a minimum spanning tree for V .We further show that similar localized techniques can be used to construct, for a given unit disk graph G = (V,E), a planar Cdel(1+")(1+π 2 )-spanner for G of maximum degree O(1) and total weight O(!(MST)). Here Cdel denotes the stretch factor of the unit Delaunay triangulation for V . Both constructions can be completed in O(1) communication rounds, and require each node to know its own coordinates.
dc.date 2010
dc.format Villanova Faculty Authorship
dc.identifier vudl:175689
dc.source Ad Hoc and Sensor Wireless Networks 9(3-4), Apri 2010, 305-328.
dc.language en
license.mdRef http://digital.library.villanova.edu/copyright.html
agent.name Falvey Memorial Library, Villanova University
KHL
has_thumbnail true
THUMBNAIL_contentDigest_type MD5
THUMBNAIL_contentDigest_digest 203c69e18f4f46c81e9892448d2c07cd
THUMBNAIL_contentLocation_type INTERNAL_ID
THUMBNAIL_contentLocation_ref http://hades-vm.library.villanova.edu:8088/fedora/get/vudl:175689/THUMBNAIL/2013-01-22T04:55:28.156Z
relsext.hasModel info:fedora/vudl-system:CoreModel
info:fedora/vudl-system:CollectionModel
info:fedora/vudl-system:ResourceCollection
relsext.itemID oai:digital.library.villanova.edu:vudl:175689
relsext.isMemberOf info:fedora/vudl:175631
relsext.hasLegacyURL http://digital.library.villanova.edu/Villanova%20Digital%20Collection/Faculty%20Fulltext/Damian%20Mirela/DamianMirela-37cd33f0-6320-468e-b753-3ee56f42d4b7.xml
relsext.sortOn title
relsext.sequence vudl:175631#20
_version_ 1696862383710928896
score 13.990891
subpages