Connectivity and inference problems for temporal networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Connectivity and inference problems for temporal networks

Full text

Pdf (1.06 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-second annual ACM symposium on Theory of computing table of contents

Portland, Oregon, United States

Pages: 504 - 513

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

David Kempe	Department of Computer Science, Cornell University, Ithaca NY
Jon Kleinberg	Department of Computer Science, Cornell University, Ithaca NY
Amit Kumar	Department of Computer Science, Cornell University, Ithaca NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 47, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/335305.335364 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	N. Bailey, The Mathematical Theory of Infectious Diseases and its Applications, Hafner Press, 1975.
	2	B. Baker, R. Shostak, "Gossips and telephones," Discrete Mathematics 2(1972), pp. 191-193.
	3	K. Berman, "Vulnerability of scheduled networks and a generalization of Menger's Theorem," Networks 28(1996), pp. 125-134.
	4	R. Bumby, "A problem with telephones," SIAM J. Algebraic and Discrete Methods 2(1981), pp. 18-31.
	5	A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Stuygis, D. Swinehart, D. Terry, "Epidemic algorithms for replicated database maintenance," Proc. A CM Symp. on Operating Systems Principles, 1987.
	6	S. Fortune, J. Hopcroft, J. Wyllie, "The directed subgraph homeomorphism problem," Theoretical Computer Science 10(1980), pp. 111-121.
	7	Venkatesan Guruswami , Sanjeev Khanna , Rajmohan Rajaraman , Bruce Shepherd , Mihalis Yannakakis, Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.19-28, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301262]
	8	A. Hajnal, E. Miller, E. Szemer~di, "A cure for the telephone disease," Canadian Math. Bulletin 15(1972), pp. 447-450.
	9	S. Hedetniemi, S. Hedetniemi, A. Liestman, "A survey'of gossiping and broadcasting in communication networks," Networks 18(1988), pp. 319-349.
	10	R.M. Karp, "On the computational complexity of combinatorial problems," Networks 5(1975), pp. 45-68.
	11	K. Kuratowski, "Sur le probl~me des courbes gauches en topologie," Fundam. Math. 15 (1930), pp. 271-283.
	12	Chung-Lun Li , Thomas S. McCormick , David Simich-Levi, The complexity of finding two disjoint paths with min-max objective function, Discrete Applied Mathematics, v.26 n.1, p.105-115, Jan. 1990 [doi>10.1016/0166-218X(90)90024-7]
	13	K. Menger, "Zur allgemeinen Kurventheorie," Fundam. Math. 19(1927), pp. 96-115.
	14	Y. Minsky, personal communication, April 1999.
	15	R. Ravi, "Rapid rumor ramification: Approximating the minimum broadcast time," Proc. IEEE FOCS, 1994.
	16	R. van Renesse, Y. Minsky, M. Hayden, "A gossip-style failure-detection service," Proc. IFIP 1996.
	17	Neil Robertson , P. D. Seymour, Graph minors. XIII: the disjoint paths problem, Journal of Combinatorial Theory Series B, v.63 n.1, p.65-110, Jan. 1995 [doi>10.1006/jctb.1995.1006]
	18	R. Tijdeman, "On a telephone problem," Nieuw Arch. Wisk. 19(1971), pp. 188-192.

CITED BY 6

	David Kempe , Jon Kleinberg , Alan Demers, Spatial gossip and resource location protocols, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.163-172, July 2001, Hersonissos, Greece
	Stephen Eubank, Scalable, efficient epidemiological simulation, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain
	Gueorgi Kossinets , Jon Kleinberg , Duncan Watts, The structure of information pathways in a social communication network, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA
	Augustin Chaintreau , Abderrahmen Mtibaa , Laurent Massoulie , Christophe Diot, The diameter of opportunistic mobile networks, Proceedings of the 2007 ACM CoNEXT conference, December 10-13, 2007, New York, New York
	Abderrahmen Mtibaa , Augustin Chaintreau , Jason LeBrun , Earl Oliver , Anna-Kaisa Pietilainen , Christophe Diot, Are you moved by your social network application?, Proceedings of the first workshop on Online social networks, August 18-18, 2008, Seattle, WA, USA
	Jerry Scripps , Pang-Ning Tan , Abdol-Hossein Esfahanian, Measuring the effects of preprocessing decisions and network forces in dynamic network analysis, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, June 28-July 01, 2009, Paris, France