Abstract
A linear time algorithm for determining the maximal number of collision-free transmissions in an arbitrary series-parallel network is developed. The method operates by a recursive contraction of the network to a single edge; during this contraction process, information is retained concerning each of the subnetworks which has been eliminated. This efficient solution contrasts with the known NP-completeness of the problem for general networks.
on leave from Department of Computer and Information Science University of Oregon Eugene, Oregon, 97403 U.S.A.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
N. Abramson, "The ALOHA System — Another Alternative for Computer Communications", Proc. AFIPS FJCC 37 (1970).
R.J. Duffin, "Topology of series-parallel networks", J. Math. Anal. Appl. 10 (1965) 303–318.
S. Even, O. Goldreich and P. Tong, "On the NP-completeness of certain network testing problems", TR 230, Computer Science Department, Technion, Haifa, Israel.
A.M. Farley, "Networks immune to isolated failures", Networks 11 (1981) 255–268.
A.M. Farley and A. Proskurowski, "Networks immune to isolated line failures", Networks 12 (1982) 393–403.
A.M. Farley and A. Proskurowski, "On computing the open irredundance number of a tree", Proceedings of the Second West Coast Conference on Computing in Graph Theory, Eugene OR, 1983, proceedings to appear, also Technical Report UO-CIS-TR-83-/4, Dept. of Computer and Information Science, University of Oregon, 1983.
A.M. Farley and N. Shacham, "Senders in Broadcast Networks: Open Irredundancy in Graphs", Congressus Numerantium 38 (1983) 47–57.
E.M. Neufeld and C.J. Colbourn, "The most reliable series-parallel networks", Networks, to appear.
D.J. Rose, "On simple characterizations of k-trees", Discrete Math. 7 (1974) 317–322.
J.A. Wald and C.J. Colbourn, "Steiner trees, partial 2-trees, and minimum IFI networks", Networks 13 (1983) 159–167.
J.A. Wald and C.J. Colbourn, "Steiner trees in probabilistic networks", Microelectronics and Reliability 23 (1983) 837–840.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1984 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Colbourn, C.J., Proskurowski, A. (1984). Concurrent transmissions in broadcast networks. In: Paredaens, J. (eds) Automata, Languages and Programming. ICALP 1984. Lecture Notes in Computer Science, vol 172. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-13345-3_11
Download citation
DOI: https://doi.org/10.1007/3-540-13345-3_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-13345-2
Online ISBN: 978-3-540-38886-9
eBook Packages: Springer Book Archive