Broadcasting in weighted trees under the postal model

Given a weighted graph G=(V,E), the broadcasting problem is to find a broadcast center such that the maximum communication time from the center to all vertices is minimized. For this problem, Slater et al. [29] proposed an O(n)-time algorithm in unweighted trees and Koh and Tcha [23] designed an O(n...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2016-03, Vol.621, p.73-81
Main Authors: Su, Yu-Hsuan, Lin, Ching-Chi, Lee, D.T.
Format: Article
Language:English
Subjects:
Algorithm
Algorithms
Broadcast center
Broadcasting
Computer simulation
Graph theory
Graphs
Mathematical models
Optimization
Postal model
Trees
Weighted tree
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c373t-c98e69c89feefa221bccbcc0ceab6490bca303df5df54e45bd446e782fa7347b3
cites cdi_FETCH-LOGICAL-c373t-c98e69c89feefa221bccbcc0ceab6490bca303df5df54e45bd446e782fa7347b3
container_end_page 81
container_issue
container_start_page 73
container_title Theoretical computer science
container_volume 621
creator Su, Yu-Hsuan
Lin, Ching-Chi
Lee, D.T.
description Given a weighted graph G=(V,E), the broadcasting problem is to find a broadcast center such that the maximum communication time from the center to all vertices is minimized. For this problem, Slater et al. [29] proposed an O(n)-time algorithm in unweighted trees and Koh and Tcha [23] designed an O(nlog⁡n)-time algorithm in unweighted trees under the telephone model. In this paper, we strengthen the results of Slater et al. by showing an O(n)-time algorithm in weighted trees under the postal model. The algorithm computes the set of broadcast centers, determines the broadcast time of the broadcast centers, and an optimal broadcast scheme from one of the centers to all vertices in the tree. We further show that the broadcast time of any vertex in the tree can also be determined in O(n) time.
doi_str_mv 10.1016/j.tcs.2016.01.031
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_1793266243</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0304397516000554</els_id><sourcerecordid>1793266243</sourcerecordid><originalsourceid>FETCH-LOGICAL-c373t-c98e69c89feefa221bccbcc0ceab6490bca303df5df54e45bd446e782fa7347b3</originalsourceid><addsrcrecordid>eNp9kEtLAzEUhYMoWKs_wF2WbmbMa5IJrrT4goIbXYdMcqdNmc7UJFX896bUtZcD9y7OuXA-hK4pqSmh8nZTZ5dqVs6a0JpweoJmtFW6YkyLUzQjnIiKa9Wco4uUNqRMo-QMNQ9xst7ZlMO4wmHE3xBW6wwe5wiQ8H70EHFeA95NKdsBbycPwyU66-2Q4Opvz9HH0-P74qVavj2_Lu6XleOK58rpFqR2re4BessY7ZwrIg5sJ4UmnbOccN83RQJE03khJKiW9VZxoTo-RzfHv7s4fe4hZbMNycEw2BGmfTJUac6kZIIXKz1aXZxSitCbXQxbG38MJeaAyGxMQWQOiAyhpiAqmbtjBkqHrwDRJBdgdOBDBJeNn8I_6V_F9m9v</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1793266243</pqid></control><display><type>article</type><title>Broadcasting in weighted trees under the postal model</title><source>ScienceDirect Freedom Collection 2022-2024</source><creator>Su, Yu-Hsuan ; Lin, Ching-Chi ; Lee, D.T.</creator><creatorcontrib>Su, Yu-Hsuan ; Lin, Ching-Chi ; Lee, D.T.</creatorcontrib><description>Given a weighted graph G=(V,E), the broadcasting problem is to find a broadcast center such that the maximum communication time from the center to all vertices is minimized. For this problem, Slater et al. [29] proposed an O(n)-time algorithm in unweighted trees and Koh and Tcha [23] designed an O(nlog⁡n)-time algorithm in unweighted trees under the telephone model. In this paper, we strengthen the results of Slater et al. by showing an O(n)-time algorithm in weighted trees under the postal model. The algorithm computes the set of broadcast centers, determines the broadcast time of the broadcast centers, and an optimal broadcast scheme from one of the centers to all vertices in the tree. We further show that the broadcast time of any vertex in the tree can also be determined in O(n) time.</description><identifier>ISSN: 0304-3975</identifier><identifier>EISSN: 1879-2294</identifier><identifier>DOI: 10.1016/j.tcs.2016.01.031</identifier><language>eng</language><publisher>Elsevier B.V</publisher><subject>Algorithm ; Algorithms ; Broadcast center ; Broadcasting ; Computer simulation ; Graph theory ; Graphs ; Mathematical models ; Optimization ; Postal model ; Trees ; Weighted tree</subject><ispartof>Theoretical computer science, 2016-03, Vol.621, p.73-81</ispartof><rights>2016 Elsevier B.V.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c373t-c98e69c89feefa221bccbcc0ceab6490bca303df5df54e45bd446e782fa7347b3</citedby><cites>FETCH-LOGICAL-c373t-c98e69c89feefa221bccbcc0ceab6490bca303df5df54e45bd446e782fa7347b3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Su, Yu-Hsuan</creatorcontrib><creatorcontrib>Lin, Ching-Chi</creatorcontrib><creatorcontrib>Lee, D.T.</creatorcontrib><title>Broadcasting in weighted trees under the postal model</title><title>Theoretical computer science</title><description>Given a weighted graph G=(V,E), the broadcasting problem is to find a broadcast center such that the maximum communication time from the center to all vertices is minimized. For this problem, Slater et al. [29] proposed an O(n)-time algorithm in unweighted trees and Koh and Tcha [23] designed an O(nlog⁡n)-time algorithm in unweighted trees under the telephone model. In this paper, we strengthen the results of Slater et al. by showing an O(n)-time algorithm in weighted trees under the postal model. The algorithm computes the set of broadcast centers, determines the broadcast time of the broadcast centers, and an optimal broadcast scheme from one of the centers to all vertices in the tree. We further show that the broadcast time of any vertex in the tree can also be determined in O(n) time.</description><subject>Algorithm</subject><subject>Algorithms</subject><subject>Broadcast center</subject><subject>Broadcasting</subject><subject>Computer simulation</subject><subject>Graph theory</subject><subject>Graphs</subject><subject>Mathematical models</subject><subject>Optimization</subject><subject>Postal model</subject><subject>Trees</subject><subject>Weighted tree</subject><issn>0304-3975</issn><issn>1879-2294</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2016</creationdate><recordtype>article</recordtype><recordid>eNp9kEtLAzEUhYMoWKs_wF2WbmbMa5IJrrT4goIbXYdMcqdNmc7UJFX896bUtZcD9y7OuXA-hK4pqSmh8nZTZ5dqVs6a0JpweoJmtFW6YkyLUzQjnIiKa9Wco4uUNqRMo-QMNQ9xst7ZlMO4wmHE3xBW6wwe5wiQ8H70EHFeA95NKdsBbycPwyU66-2Q4Opvz9HH0-P74qVavj2_Lu6XleOK58rpFqR2re4BessY7ZwrIg5sJ4UmnbOccN83RQJE03khJKiW9VZxoTo-RzfHv7s4fe4hZbMNycEw2BGmfTJUac6kZIIXKz1aXZxSitCbXQxbG38MJeaAyGxMQWQOiAyhpiAqmbtjBkqHrwDRJBdgdOBDBJeNn8I_6V_F9m9v</recordid><startdate>20160328</startdate><enddate>20160328</enddate><creator>Su, Yu-Hsuan</creator><creator>Lin, Ching-Chi</creator><creator>Lee, D.T.</creator><general>Elsevier B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20160328</creationdate><title>Broadcasting in weighted trees under the postal model</title><author>Su, Yu-Hsuan ; Lin, Ching-Chi ; Lee, D.T.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c373t-c98e69c89feefa221bccbcc0ceab6490bca303df5df54e45bd446e782fa7347b3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2016</creationdate><topic>Algorithm</topic><topic>Algorithms</topic><topic>Broadcast center</topic><topic>Broadcasting</topic><topic>Computer simulation</topic><topic>Graph theory</topic><topic>Graphs</topic><topic>Mathematical models</topic><topic>Optimization</topic><topic>Postal model</topic><topic>Trees</topic><topic>Weighted tree</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Su, Yu-Hsuan</creatorcontrib><creatorcontrib>Lin, Ching-Chi</creatorcontrib><creatorcontrib>Lee, D.T.</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Theoretical computer science</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Su, Yu-Hsuan</au><au>Lin, Ching-Chi</au><au>Lee, D.T.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Broadcasting in weighted trees under the postal model</atitle><jtitle>Theoretical computer science</jtitle><date>2016-03-28</date><risdate>2016</risdate><volume>621</volume><spage>73</spage><epage>81</epage><pages>73-81</pages><issn>0304-3975</issn><eissn>1879-2294</eissn><abstract>Given a weighted graph G=(V,E), the broadcasting problem is to find a broadcast center such that the maximum communication time from the center to all vertices is minimized. For this problem, Slater et al. [29] proposed an O(n)-time algorithm in unweighted trees and Koh and Tcha [23] designed an O(nlog⁡n)-time algorithm in unweighted trees under the telephone model. In this paper, we strengthen the results of Slater et al. by showing an O(n)-time algorithm in weighted trees under the postal model. The algorithm computes the set of broadcast centers, determines the broadcast time of the broadcast centers, and an optimal broadcast scheme from one of the centers to all vertices in the tree. We further show that the broadcast time of any vertex in the tree can also be determined in O(n) time.</abstract><pub>Elsevier B.V</pub><doi>10.1016/j.tcs.2016.01.031</doi><tpages>9</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0304-3975
ispartof Theoretical computer science, 2016-03, Vol.621, p.73-81
issn 0304-3975
1879-2294
language eng
recordid cdi_proquest_miscellaneous_1793266243
source ScienceDirect Freedom Collection 2022-2024
subjects Algorithm
Algorithms
Broadcast center
Broadcasting
Computer simulation
Graph theory
Graphs
Mathematical models
Optimization
Postal model
Trees
Weighted tree
title Broadcasting in weighted trees under the postal model
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-06T20%3A31%3A56IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Broadcasting%20in%20weighted%20trees%20under%20the%20postal%20model&rft.jtitle=Theoretical%20computer%20science&rft.au=Su,%20Yu-Hsuan&rft.date=2016-03-28&rft.volume=621&rft.spage=73&rft.epage=81&rft.pages=73-81&rft.issn=0304-3975&rft.eissn=1879-2294&rft_id=info:doi/10.1016/j.tcs.2016.01.031&rft_dat=%3Cproquest_cross%3E1793266243%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c373t-c98e69c89feefa221bccbcc0ceab6490bca303df5df54e45bd446e782fa7347b3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1793266243&rft_id=info:pmid/&rfr_iscdi=true