research-article

Broadcasting in necklace graphs

Authors:

Hovhannes Harutyunyan,

Edward MaraachlianAuthors Info & Claims

C3S2E '09: Proceedings of the 2nd Canadian Conference on Computer Science and Software Engineering

Pages 253 - 256

https://doi.org/10.1145/1557626.1557667

Published: 19 May 2009 Publication History

Abstract

Broadcasting is an information dissemination problem in a connected network, in which one node, called the originator, disseminates a message to all other nodes by placing a series of calls along the communication lines of the network. Once informed, the nodes aid the originator in distributing the message. Finding the broadcast time of any vertex in an arbitrary graph is NP-complete. The polynomial time solvability is shown only for trees and unicyclic graphs. In this paper we consider necklace graphs. We present a linear algorithm to find the broadcast time of an arbitrary necklace graph.

References

[1]

A. Bar-Noy, S. Guha, J. Naor and B. Schieber. Multicasting in Heterogeneous Networks, Proc. of ACM Symp. on Theory of Computing, STOC'98, 1998.

Digital Library

[2]

R. Beier, J. F. Sibeyn, A powerful heuristic for telephone gossiping, Proc. of the 7th International Colloquium on Structural Information&Communication Complexity, SIROCCO'00, L'Aquila, Italy, 2000, pp. 17--36.

[3]

M. Elkin, G. Kortsarz. A combinatorial logarithmic approximation algorithm for the directed telephone broadcast problem, Proc. of ACM Symp. on Theory of Computing, STOC'02, 2002, pp. 438--447.

Digital Library

[4]

M. Elkin and G. Kortsarz, Sublogarithmic approximation for telephone multicast: path out of jungle, Proc. of Symposium on Discrete Algorithms, SODA'03, Baltimore, Maryland, 2003, pp. 76--85.

Digital Library

[5]

P. Fraigniaud, E. Lazard, Methods and problems of communication in usual networks, Discrete Appl. Math. 53 (1994) 79--133.

Digital Library

[6]

P. Fraigniaud, S. Vial, Approximation algorithms for broadcasting and gossiping, J. Parallel and Distrib. Comput. 43(1) (1997) 47--55.

Digital Library

[7]

P. Fraigniaud, S. Vial, Comparison of Heuristics for One-to-All and All-to-All Communication in Partial Meshes, Parallel Processing Letters, 9(1), 1999, pp. 9--20.

[8]

H. A. Harutyunyan, E. Maraachlian, On Broadcasting in Unicyclic Graphs, Journal of Combinatorial Optimization Vol 16,(2008), pp. 307--322.

[9]

H. A. Harutyunyan, B. Shao, An Efficient Heuristic for Broadcasting in Networks, Journal of Parallel and Distributed Computing 66(1), 2006, pp. 68--76.

Digital Library

[10]

S. M Hedetniemi, S. T. Hedetniemi, A. L. Liestman, A survey of gossiping and broadcasting in communication networks, Networks, 18 (1988) 319--349.

[11]

J. Hromkovic, R. Klasing, B. Monien, R. Peine, Dissemination of information in interconnection networks, in: Combinatorial Network Theory, D.-Z. Du, D. F. Hsu(eds.), Kluwer Academic Publishers, 1996, pp. 125--212.

[12]

J Hromkovic, R. Klasing, A. Pelc, P. Ruzicka, W. Unger, Dissemination of Information in Communication Networks - Broadcasting, Gossiping, Leader Election, and Fault-Tolerance, Springer 2005.

Digital Library

[13]

A. Jakoby, R. Reischuk, C. Schindelhauer, The Complexity of Broadcasting in Planar and Decomposable Graphs, Discrete Applied athematics, Vol. 83, 1998, 179--206.

Digital Library

[14]

D. Johnson and M. Garey, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, CA, 1979).

Digital Library

[15]

M. Middendorf, Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2, Information Processing Letters, 46(6): 281--287, 1993.

Digital Library

[16]

R. Ravi, Rapid Rumor Ramification: Approximating the minimum broadcast time, Proc. of 35th Symposium on Foundation of Computer Science, FOCS'94, 1994, pp. 202--213.

Digital Library

[17]

P. J. Slater, E. J. Cockayne, S. T. Hedetniemi, Information dissemination in trees, SIAM J. Comput. 10(4) (1981) 692--701.

Cited By

Harutyunyan HHovhannisyan NMaraachlian E(2023)Broadcasting in chains of rings2023 Fourteenth International Conference on Ubiquitous and Future Networks (ICUFN)10.1109/ICUFN57995.2023.10201234(506-511)Online publication date: 4-Jul-2023
https://doi.org/10.1109/ICUFN57995.2023.10201234
Čevnik MźErovnik J(2017)Broadcasting on cactus graphsJournal of Combinatorial Optimization10.1007/s10878-015-9957-833:1(292-316)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1007/s10878-015-9957-8
Bhabak PHarutyunyan H(2014)Broadcast Problem in Hypercube of TreesFrontiers in Algorithmics10.1007/978-3-319-08016-1_1(1-12)Online publication date: 2014
https://doi.org/10.1007/978-3-319-08016-1_1

Index Terms

Broadcasting in necklace graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows

Recommendations

Broadcasting on cactus graphs

Broadcasting is the process of dissemination of a message from one vertex (called originator) to all other vertices in the graph. This task is accomplished by placing a sequence of calls between neighboring vertices, where one call requires one unit of ...
Broadcasting in Harary-Like Graphs
CSE '14: Proceedings of the 2014 IEEE 17th International Conference on Computational Science and Engineering

Broadcasting is an information dissemination problem in a connected graph in which one vertex, called the originator, must distribute a message to all other vertices by placing a series of calls along the edges of the graph. Every time the informed ...
k-tuple domination in graphs

In a graph G, a vertex is said to dominate itself and all of its neighbors. For a fixed positive integer k, the k-tuple domination problem is to find a minimum sized vertex subset in a graph such that every vertex in the graph is dominated by at least k ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

C3S2E '09: Proceedings of the 2nd Canadian Conference on Computer Science and Software Engineering

May 2009

266 pages

ISBN:9781605584010

DOI:10.1145/1557626

Editors:
Bipin C. Desai
Concordia University
,
Carson K. Leung
University of Manitoba

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

BytePress
Concordia University: Concordia University

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 May 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

C3S2E '09

Sponsor:

Concordia University

C3S2E '09: Proceedings of the 2009 C3S2E conference

May 19 - 21, 2009

Quebec, Montreal, Canada

Acceptance Rates

Overall Acceptance Rate 12 of 42 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
148
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Harutyunyan HHovhannisyan NMaraachlian E(2023)Broadcasting in chains of rings2023 Fourteenth International Conference on Ubiquitous and Future Networks (ICUFN)10.1109/ICUFN57995.2023.10201234(506-511)Online publication date: 4-Jul-2023
https://doi.org/10.1109/ICUFN57995.2023.10201234
Čevnik MźErovnik J(2017)Broadcasting on cactus graphsJournal of Combinatorial Optimization10.1007/s10878-015-9957-833:1(292-316)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1007/s10878-015-9957-8
Bhabak PHarutyunyan H(2014)Broadcast Problem in Hypercube of TreesFrontiers in Algorithmics10.1007/978-3-319-08016-1_1(1-12)Online publication date: 2014
https://doi.org/10.1007/978-3-319-08016-1_1

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents