<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>
doi: 10.1137/0210052
Summary: In large organizations there is frequently a need to pass information from one place, e.g., the president's office or company headquarters, to all other divisions, departments or employees. This is often done along organizational reporting lines. Insofar as most organizations are structured in a hierarchical or treelike fashion, this can be described as a process of information dissemination in trees. In this paper we present an algorithm which determines the amount of time required to pass, or to broadcast, a unit of information from an arbitrary vertex to every other vertex in a tree. As a byproduct of this algorithm we determine the broadcast center of a tree, i.e., the set of all vertices from which broadcasting can be accomplished in the least amount of time. It is shown that the subtree induced by the broadcast center of a tree is always a star with two or more vertices. We also show that the problem of determining the minimum amount of time required to broadcast from an arbitrary vertex in an arbitrary graph is NP-complete.
Graph theory (including graph drawing) in computer science, Analysis of algorithms and problem complexity, Applications of graph theory to circuits and networks, Deterministic network models in operations research, broadcasting, graph information dissemination, NP-complete
Graph theory (including graph drawing) in computer science, Analysis of algorithms and problem complexity, Applications of graph theory to circuits and networks, Deterministic network models in operations research, broadcasting, graph information dissemination, NP-complete
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 163 | |
popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |