Sparse Covers for Planar Graphs and Graphs that Exclude a Fixed Minor
dc.contributor.author | Busch, Costas | |
dc.contributor.author | Tirthapura, Srikanta | |
dc.contributor.department | Computer Science | |
dc.contributor.department | Electrical and Computer Engineering | |
dc.date | 2018-04-29T19:34:48.000 | |
dc.date.accessioned | 2020-06-30T02:02:36Z | |
dc.date.available | 2020-06-30T02:02:36Z | |
dc.date.copyright | Tue Jan 01 00:00:00 UTC 2013 | |
dc.date.issued | 2014-07-01 | |
dc.description.abstract | <p>We consider the construction of sparse covers for planar graphs and other graphs that exclude a fixed minor. We present an algorithm that gives a cover for the γ-neighborhood of each node. For planar graphs, the cover has radius less than 16γ and degree no more than 18. For every n node graph that excludes a minor of a fixed size, we present an algorithm that yields a cover with radius no more than 4γ and degree O(logn).</p> <p>This is a significant improvement over previous results for planar graphs and for graphs excluding a fixed minor; in order to obtain clusters with radius O(γ), it was required to have the degree polynomial in n. Our algorithms are based on a recursive application of a basic routine called shortest-path clustering, which seems to be a novel approach to the construction of sparse covers.</p> <p>Since sparse covers have many applications in distributed computing, including compact routing, distributed directories, synchronizers, and Universal TSP, our improved cover construction results in improved algorithms for all these problems, for the class of graphs that exclude a fixed minor.</p> | |
dc.description.comments | <p>This is a manuscript of an article published as Busch, Costas, Ryan LaFortune, and Srikanta Tirthapura. "Sparse Covers for Planar Graphs and Graphs that Exclude a Fixed Minor." Algorithmica 69, no. 3 (2014): 658-684. The final publication is available at Springer via DOI: <a href="http://dx.doi.org/10.1007/s00453-013-9757-4" target="_blank">10.1007/s00453-013-9757-4</a>. Posted with permission.</p> | |
dc.format.mimetype | application/pdf | |
dc.identifier | archive/lib.dr.iastate.edu/ece_pubs/180/ | |
dc.identifier.articleid | 1179 | |
dc.identifier.contextkey | 12012232 | |
dc.identifier.s3bucket | isulib-bepress-aws-west | |
dc.identifier.submissionpath | ece_pubs/180 | |
dc.identifier.uri | https://dr.lib.iastate.edu/handle/20.500.12876/21006 | |
dc.language.iso | en | |
dc.source.bitstream | archive/lib.dr.iastate.edu/ece_pubs/180/2014_Tirthapura_SparseCovers.pdf|||Fri Jan 14 21:35:21 UTC 2022 | |
dc.source.uri | 10.1007/s00453-013-9757-4 | |
dc.subject.disciplines | Computer Sciences | |
dc.subject.disciplines | Electrical and Computer Engineering | |
dc.subject.disciplines | Software Engineering | |
dc.subject.keywords | Shortest path clustering | |
dc.title | Sparse Covers for Planar Graphs and Graphs that Exclude a Fixed Minor | |
dc.type | article | |
dc.type.genre | article | |
dspace.entity.type | Publication | |
relation.isAuthorOfPublication | b0235db2-0a72-4dd1-8d5f-08e5e2e2bf7d | |
relation.isOrgUnitOfPublication | f7be4eb9-d1d0-4081-859b-b15cee251456 | |
relation.isOrgUnitOfPublication | a75a044c-d11e-44cd-af4f-dab1d83339ff |
File
Original bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- 2014_Tirthapura_SparseCovers.pdf
- Size:
- 1.26 MB
- Format:
- Adobe Portable Document Format
- Description: