Luisa Gargano - Papers in

NETWORKS AND GRAPHS
COMBINATORIAL SEARCH
COMBINATORICS
INFORMATION THEORY AND APPLICATIONS
VOLUMES EDITED

NETWORKS AND GRAPHS

• "Label Propagation Algorithm: A Semi-Synchronous Approach", International Journal of Social Network Mining, to appear, (with G. Cordasco).

• ''Optimal Time Data Gathering in Wireless Networks with Omni--Directional Antennas'', Proceedings of 18th International Colloquium on Structural Information and Communication Complexity Gdansk, Poland, June 26-29, 2011, (with J-C. Bermond, S. Perennes, A. Rescigno, U. Vaccaro).

• Community Detection via Semi-Synchronous Label Propagation Algorithms, Proceedings of IEEE International Workshop on Business Applications of Social Network Analysis (BASNA-10), Bangalore, India, December 2010, (with G. Cordasco).

• ''Gathering with Minimum Completion Time in Sensor Tree Networks", Journal of Interconnection Networks, vol. 11, pp. 1-33, 2010, (with J-C.Bermond, A.A.Rescigno).

• ''Navigable Small-World Networks with Few Random Bits'', Theoretical Computer Science, Vol. 410 , Issue 47-49, pp. 4975-4988, 2009, (with G. Cordasco).

• ”Collision–Free Path Coloring with Application to Minimum–Delay Gathering in Sensor Networks”, Discrete Applied Mathematics, vol. 157(8), pp. 1858-1872, 2009, (with A. Rescigno).

• "Gathering with Minimum Delay in Sensor Networks", Proceedings of 15th International Colloquium on Structural Information and Communication, Complexity (SIROCCO 2008), LNCS 5058, (with J.-C. Bermond and A. Rescigno)

• ``F-Chord: improved uniform routing on Chord'', NETWORKS, Vol. 52 No. 4, pp. 325-332, 2008, (with G. Cordasco, M. Hammar, A. Negro, V. Scarano)

• "Degree-Optimal Routing for P2P Systems", Theory of Computing Systems, to appear, (with G. Chiola, G. Cordasco, M. Hammar, A. Negro, V. Scarano).

• "Optimizing the finger table in Chord-like DHTs", Concurrency and Computation: Practice and Experience , Vol. 20, issue 6, 2008, pp. 643-657. (with G. Chiola, G. Cordasco, A. Negro, V. Scarano).

• "Time Optimal Gathering in Sensor Networks", Keynote Talk, Proceedings of Structural Information and Communication, Complexity 14th International Colloquium, SIROCCO 2007, Castiglioncello, Italy, June 5-8, 2007, LNCS 4474, Springer Verlag.

• "How Much Independent Should Individual Contacts be to Form a Small-World?'', Proc. 17th International Symposium on Algorithms and Computation (ISAAC 2006), T. Asano (Ed.), Springer-Verlag LNCS 4288, pp. 328-338, 2006, (with G. Cordasco).

• ''Optimally Fast Data Gathering in Sensor Networks'', Proceedings of 31st International Symposium on Mathematical Foundations of Computer Science (MFCS 2006), Lecture Notes in Computer Science , Vol. 4162, pp. 399-411, Springer Verlag, (with A.A. Rescigno).

• "Asynchronous deterministic rendezvous in graphs'', Theoretical Computer Science, vol. 355, pp. 315-326, 2006,
  preliminary version in: Proc. 30th International Symposium on Mathematical Foundations of Computer Science (MFCS 2005), (with G. De Marco, E. Kranakis, D. Krizanc, A. Pelc, U. Vaccaro).

• ``Optimizing the finger table in Chord-like DHTs'', Third International Workshop on Hot Topics in Peer-to-Peer Systems, in conjunction with IPDPS'06, Rhodes Island, Greece, April 2006, (with G. Chiola, G. Cordasco, A. Negro, V. Scarano)

• ``Overlay networks with class'', Proceedings of 8th International Symposium on Parallel Architectures,Algorithms and Networks (ISPAN 2005), IEEE, 2005, (with G. Chiola, G. Cordasco, A. Negro, V. Scarano)

• ``Degree--Optimal Deterministic Routing for P2p Systems'', Proceedings of Tenth IEEE Symposium on Computers and Communications (ISCC 2005), IEEE, (with G. Cordasco, M. Hammar, V. Scarano)

• ''Spanning Spiders and light-splitting switches'', Discrete Mathematics, vol. 285, Issue 1-3, pp. 83-95, 2004,
  (with M. Hammar, P. Hell, L. Stacho, and U. Vaccaro).

• ``Limiting Flooding Expenses in On-demand Source-Initiated Protocols for Mobile Wireless Networks", Proceedings of IPDPS 2004 - 4th International Workshop on Wireless, Mobile and Ad Hoc Networks (WMAN), 2004, (with M. Hammar and A. Ostlin).

• ``F-Chord: improved uniform routing on Chord'', Proceedings of Sirocco 2004, June 21-23, 2004, Slovakia, (with G. Cordasco, M. Hammar, A. Negro, V. Scarano)

• ``Non-uniform deterministic routing on F-Chord'', Proceedings of International Workshop on Hot Topics in Peer-to-Peer Systems, IEEE Press, (with G. Cordasco, M. Hammar, A. Negro, V. Scarano).

• ``Brief Announcement: Degree--Optimal Deterministic Routing for P2p Systems'', Proceedings of PODC 2004, Brief Announcment , July 25-28, 2004, St John's, Canada, (with G. Cordasco, M. Hammar, V. Scarano)

• ''There are Spanning Spiders in Dense Graphs (and we know how to find them)'', Proceedings of 30th International Colloquium on Automata, Languages, and Programming (ICALP' 2003), (with M. Hammar).

• ``Multicasting to Groups in Optical Networks'', Proceedings IPDPS 2003 - 3rd International Workshop on Wireless, Mobile and Ad Hoc Networks (WMAN), 2003, (with A. Rescigno and U. Vaccaro).

• ``Spanning Trees with Bounded Number of Branch Vertices'', Proceedings of ICALP' 2002, P. Widmayer et al. (Eds.), Lectures Notes in Computer Science, vol. 2380, pp. 355-365, Springer-Verlag, 2002, (with P. Hell, L. Stacho, and U. Vaccaro).

• ``Colouring All Directed Paths in a Symmetric Tree with an Application to Optical Networks'', Journal of Graph Theory, 2001, 183--196. (with S. Perennes and P. Hell).

• ``Concurrent Multicast in Weighted Networks'', Theoretical Computer Science, vol. 259, no. 1-2, pp. 359-377, 2001,
  an extended abstract appeared in the proceeedings of 6-th Scandinavian Workshop on Algorithm Theory (SWAT'98), Stockholm, Sweden, July 8-10 1998, (with G. De Marco ed U. Vaccaro).

• ``Sparse and Limited Wavelenght Conversion in Tree Networks'', Theoretical Computer Science, 2001, (with V. Auletta, I. Caragiannis, C. Kaklamanis, G. Persiano)

• "Efficient Communication in Unknown Networks", NETWORKS, vol. 38, 2001, 39-49 , (with A. Pelc, S. Perennes and U. Vaccaro)

• ``Efficient Collective Communication in Optical Networks'', Theoretical Computer Science, vol. 233, 2000, 119-124, (with J.-C. Bermond, S. Perennes, A. Rescigno, and U. Vaccaro).

• ``Coloring Circular Arcs with Applications to WDM Routing", Workshop on Approximation and Randomization Algorithms in Communication Networks (ARACNE'00), July 2000, Geneva, Switzerland, (with A. Rescigno).

• ``Routing in All--Optical Networks: Algorithmic and Graph--Theoretic Problems'', tutorial, in: Numbers, Information and Complexity, I. Althofer et al. (Eds.), Kluwer Academic Publisher, pp. 555-578, Feb. 2000. (with U. Vaccaro).

• ``Limited Wavelength Conversion in All-Optical Tree Networks'', Proceedings of 25th International Colloquium on Automata, Languages, and Programming (ICALP 98), Aalborg, July 1998.

• ``Colouring All Directed Paths in a Symmetric Tree with an Application to Optical Networks'', Proceedings of 24th International Colloquium on Automata, Languages, and Programming (ICALP 97), Bologna, Italy, July 1997, (with S. Perennes and P. Hell).

• ``Efficient Collective Communication in Optical Networks'', Prooceedings of 23rd International Colloquium on Automata, Languages, and Programming (ICALP 96), Paderborn, Germany, July 1996, (with J.-C. Bermond, S. Perennes, A. Rescigno, and U. Vaccaro).

• ``Graph Problems Arising from Wavelength--Routing in All--Optical Networks'', 2nd Workshop on Optics and Computer Science (WOCS 97), Geneve, Switzerland, April 1997, (with B. Beauquier, J.-C. Bermond, P. Hell, S. Perennes, and U. Vaccaro).

• ``Fast Gossiping by Short Messages'', SIAM Journal on Computing, 27 (1998), 917 - 941
  an extended abstract appeared in: Prooceedings of 22nd International Colloquium on Automata, Languages, and Programming (ICALP 95), LNCS 944, pp. 135-146, (with J.-C. Bermond, A. Rescigno, and U. Vaccaro).

• ``Communication Complexity of Fault--Tolerant Information Diffusion'', Theoretical Computer Science, (209)1-2 (1998), 195-211, (with A. A. Rescigno).

• ``Fast Collective Communication by Packets in the Postal Model'', Networks, 31 (1998), 67-79, (with A.A. Rescigno).

• ``Optimal Sequential Gossiping by Short Messages'', Discrete Applied Math., 86 (1998) pp. 145-155, (with J.-C. Bermond and S. Perennes).

• ``Minimum Time Broadcasting in Faulty Star Networks'', Discrete Applied Math., 82 (1998), 95-117, (with A.A. Rescigno and U. Vaccaro).

• ``Communication Complexity of Gossiping by Packets'', Journal of Parallel and Distributed Computing, 45 (1997), 73--81,
  an extended abstract appeared in: Prooceedings of Fifth Scandinavian Workshop on Algorithm Theory (SWAT'96), Reykjavik, Iceland, July 3-5, 1996, (with A. Rescigno and U. Vaccaro).

• ``Fault-Tolerant Minimum Broadcast Networks'', NETWORKS, 27 (1996), 293--307, (with R. Ahlswede, H.S. Haroutunian, and L.H. Khachatrian).

  ``Reliable Broadcasting'', Discrete Applied Mathematics, vol. 53 (1994), 135-148, (with A. Liestman, J.G. Peters e D. Richards).

• ``Fault Tolerant Routing in the Star and Pancake Interconnection Networks'', Information Processing Letters, vol. 45, (1993), 315-320, (with U. Vaccaro and A. Vozella).

• ``Fault-Tolerant Hypercube Broadcasting via Information Dispersal'', NETWORKS, vol. 23, (1993), 271-282, (with A.A. Rescigno and U. Vaccaro).

• ``Tighter Time Bounds for Fault Tolerant Broadcasting and Gossiping'', NETWORKS, vol. 22 (1992), 469-486.

• ``Minimum Time Broadcast Networks Tolerating a Logarithmic Number of Faults'', SIAM J. on Discrete Mathematics, vol. 5, (1992), 178-198, (with U. Vaccaro).

• ``Time Bounds for Broadcasting in Bounded Degree Graphs'', in: Graph-Theoretic Concepts in Computer Science, M. Nagl (Ed.), Lectures Notes in Computer Science, vol. 411, pp. 19-33, Springer-Verlag, 1990. (with R. M. Capocelli and U. Vaccaro).

• ``On the Construction of Minimal Broadcast Networks'', NETWORKS, vol. 19, (1989), 673-689, (with U. Vaccaro).