SINGLE-SOURCE DILATION-BOUNDED MINIMUM SPANNING TREES

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 497
  • Download : 0
Given a set S of points in the plane, a geometric network for S is a graph G with vertex set S and straight edges. We consider a broadcasting situation, where one point r is an element of S is a designated source. Given a dilation factor delta, we ask for a geometric network G such that for every point v is an element of S there is a path from r to v in G of length at most delta vertical bar rv vertical bar, and such that the total edge length is minimized. We show that finding such a network of minimum total edge length is NP-hard, and give an approximation algorithm.
Publisher
WORLD SCIENTIFIC PUBL CO PTE LTD
Issue Date
2013-06
Language
English
Article Type
Article
Keywords

NP-HARD; GRAPHS

Citation

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, v.23, no.3, pp.159 - 170

ISSN
0218-1959
DOI
10.1142/S0218195913500052
URI
http://hdl.handle.net/10203/188665
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0