{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T06:02:21Z","timestamp":1746252141608,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540735441"},{"type":"electronic","value":"9783540735458"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-73545-8_37","type":"book-chapter","created":{"date-parts":[[2007,8,17]],"date-time":"2007-08-17T13:44:11Z","timestamp":1187358251000},"page":"372-382","source":"Crossref","is-referenced-by-count":17,"title":["Linear Algorithm for Broadcasting in Unicyclic Graphs"],"prefix":"10.1007","author":[{"given":"Hovhannes","family":"Harutyunyan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edward","family":"Maraachlian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"37_CR1","doi-asserted-by":"crossref","unstructured":"Aiello, W., Chung, F., Lu, L.: Random evolution in massive graphs. In: FOCS 2001. Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, pp. 510\u2013519 (2001)","DOI":"10.1109\/SFCS.2001.959927"},{"key":"37_CR2","doi-asserted-by":"crossref","unstructured":"Bar-Noy, A., Guha, S., Naor, J., Schieber, B.: Multicasting in Heterogeneous Networks. In: STOC 1998. Proc. of ACM Symp. on Theory of Computing (1998)","DOI":"10.1145\/276698.276857"},{"key":"37_CR3","unstructured":"Beier, R., Sibeyn, J.F.: A powerful heuristic for telephone gossiping. In: SIROCCO 2000. Proc. of the 7th International Colloquium on Structural Information & Communication Complexity, L\u2019Aquila, Italy, pp. 17\u201336 (2000)"},{"key":"37_CR4","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1002\/net.3230260302","volume":"26","author":"J.-C. Bermond","year":"1995","unstructured":"Bermond, J.-C., Fraigniaud, P., Peters, J.: Antepenultimate broadcasting. Networks\u00a026, 125\u2013137 (1995)","journal-title":"Networks"},{"key":"37_CR5","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0166-218X(92)90226-Z","volume":"36","author":"J.-C. Bermond","year":"1992","unstructured":"Bermond, J.-C., Hell, P., Liestman, A.L., Peters, J.G.: Sparse broadcast graphs. Discrete Appl. Math.\u00a036, 97\u2013130 (1992)","journal-title":"Discrete Appl. Math."},{"key":"37_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1007\/3-540-54522-0_104","volume-title":"Applied Algebra, Algebraic Algorithms and Error-Correcting Codes","author":"M.J. Dinneen","year":"1991","unstructured":"Dinneen, M.J., Fellows, M.R., Faber, V.: Algebraic constructions of efficient broadcast networks. In: Mattson, H.F., Rao, T.R.N., Mora, T. (eds.) Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. LNCS, vol.\u00a0539, pp. 152\u2013158. Springer, Heidelberg (1991)"},{"key":"37_CR7","volume-title":"IEEE GLOBECOM 1996","author":"M.B. Doar","year":"1996","unstructured":"Doar, M.B.: A better model for generating test networks. In: IEEE GLOBECOM 1996, London, IEEE Computer Society Press, Los Alamitos (1996)"},{"key":"37_CR8","doi-asserted-by":"crossref","unstructured":"Elkin, M., Kortsarz, G.: A combinatorial logarithmic approximation algorithm for the directed telephone broadcast problem. In: STOC 2002. Proc. of ACM Symp. on Theory of Computing, pp. 438\u2013447 (2002)","DOI":"10.1145\/509907.509972"},{"key":"37_CR9","unstructured":"Elkin, M., Kortsarz, G.: Sublogarithmic approximation for telephone multicast: path out of jungle. In: SODA 2003. Proc. of Symposium on Discrete Algorithms, Baltimore, Maryland, pp. 76\u201385 (2003)"},{"key":"37_CR10","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0012-365X(79)90022-0","volume":"25","author":"A.M. Farley","year":"1979","unstructured":"Farley, A.M., Hedetniemi, S.T., Proskurowski, A., Mitchell, S.: Minimum broadcast graphs. Discrete Math.\u00a025, 189\u2013193 (1979)","journal-title":"Discrete Math."},{"key":"37_CR11","doi-asserted-by":"crossref","unstructured":"Feige, U., Peleg, D., Raghavan, P., Upfal, E.: Randomized broadcast in networks. In: SIGAL 1990. Proc. of International Symposium on Algorithms, pp. 128\u2013137 (1990)","DOI":"10.1007\/3-540-52921-7_62"},{"issue":"1","key":"37_CR12","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1006\/jpdc.1997.1318","volume":"43","author":"P. Fraigniaud","year":"1997","unstructured":"Fraigniaud, P., Vial, S.: Approximation algorithms for broadcasting and gossiping. J. Parallel and Distrib. Comput.\u00a043(1), 47\u201355 (1997)","journal-title":"J. Parallel and Distrib. Comput."},{"key":"37_CR13","unstructured":"Fraigniaud, P., Vial, S.: Heuristic Algorithms for Personalized Communication Problems in Point-to-Point Networks. In: SIROCCO 1997. Proc. of the 4th Colloquium on Structural Information and Communication Complexity, pp. 240\u2013252 (1997)"},{"issue":"1","key":"37_CR14","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1142\/S0129626499000049","volume":"9","author":"P. Fraigniaud","year":"1999","unstructured":"Fraigniaud, P., Vial, S.: Comparison of Heuristics for One-to-All and All-to-All Communication in Partial Meshes. Parallel Processing Letters\u00a09(1), 9\u201320 (1999)","journal-title":"Parallel Processing Letters"},{"key":"37_CR15","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/S0166-218X(99)00108-0","volume":"98","author":"H.A. Harutyunyan","year":"1999","unstructured":"Harutyunyan, H.A., Liestman, A.L.: More broadcast graphs. Discrete Math.\u00a098, 81\u2013102 (1999)","journal-title":"Discrete Math."},{"key":"37_CR16","unstructured":"Harutyunyan, H.A., Shao, B.: An Efficient Heuristic for Broadcasting in Networks. Journal of Parallel and Distributed Computing (to appear)"},{"key":"37_CR17","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"D. Johnson","year":"1979","unstructured":"Johnson, D., Garey, M.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA (1979)"},{"key":"37_CR18","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1137\/S0895480193245923","volume":"8","author":"G. Kortsarz","year":"1995","unstructured":"Kortsarz, G., Peleg, D.: Approximation algorithms for minimum time broadcast. SIAM J. Discrete Math.\u00a08, 401\u2013427 (1995)","journal-title":"SIAM J. Discrete Math."},{"key":"37_CR19","doi-asserted-by":"crossref","unstructured":"Ravi, R.: Rapid Rumor Ramification: Approximating the minimum broadcast time. In: FOCS 1994. Proc. of 35th Symposium on Foundation of Computer Science, pp. 202\u2013213 (1994)","DOI":"10.1109\/SFCS.1994.365693"},{"issue":"4","key":"37_CR20","doi-asserted-by":"publisher","first-page":"692","DOI":"10.1137\/0210052","volume":"10","author":"P.J. Slater","year":"1981","unstructured":"Slater, P.J., Cockayne, E.J., Hedetniemi, S.T.: Information dissemination in trees. SIAM J.Comput.\u00a010(4), 692\u2013701 (1981)","journal-title":"SIAM J.Comput."},{"issue":"9","key":"37_CR21","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1109\/TC.1984.1676496","volume":"C-33","author":"P. Scheuerman","year":"1984","unstructured":"Scheuerman, P., Wu, G.: Heuristic Algorithms for Broadcasting in Point-to-Point Computer Network. IEEE Transactions on Computers\u00a0C-33(9), 804\u2013811 (1984)","journal-title":"IEEE Transactions on Computers"},{"key":"37_CR22","volume-title":"INFOCOM 1996","author":"E.W. Zegura","year":"1996","unstructured":"Zegura, E.W., Calvert, K., Bhattacharjee, S.: How to model an internetwork. In: INFOCOM 1996. Proc. The IEEE Conf. on Computer Communications, San Francisco, CA, IEEE Computer Society Press, Los Alamitos (1996)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73545-8_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T12:33:13Z","timestamp":1737376393000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73545-8_37"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540735441","9783540735458"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73545-8_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}