Finding Graph Matchings in Data Streams

1. Edmonds, J.: Maximum matching and a polyhedron with 0,1-vertices. J. Res. Nat. Bur. Standards 69, 125–130 (1965)

   MATH  MathSciNet  Google Scholar 

2. Gabow, H.N.: Data structures for weighted matching and nearest common ancestors with linking. In: Proc. ACM-SIAM Symposium on Discrete Algorithms, pp. 434–443 (1990)

   Google Scholar 

3. Hopcroft, J.E., Karp, R.M.: An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2, 225–231 (1973)

   Article  MATH  MathSciNet  Google Scholar 

4. Micali, S., Vazirani, V.: An O(\(\sqrt{V}\) E) algorithm for finding maximum matching in general graphs. In: Proc. 21st Annual IEEE Symposium on Foundations of Computer Science (1980)

   Google Scholar 

5. Drake, D.E., Hougardy, S.: Improved linear time approximation algorithms for weighted matchings. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol. 2764, pp. 14–23. Springer, Heidelberg (2003)

   Google Scholar 

6. Kalantari, B., Shokoufandeh, A.: Approximation schemes for maximum cardinality matching. Technical Report LCSR–TR–248, Laboratory for Computer Science Research, Department of Computer Science. Rutgers University (1995)

   Google Scholar 

7. Preis, R.: Linear time 1/2-approximation algorithm for maximum weighted matching in general graphs. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 259–269. Springer, Heidelberg (1999)

   Chapter  Google Scholar 

8. Muthukrishnan, S.: Data streams: Algorithms and applications (2003), available at http://athos.rutgers.edu/~muthu/stream-1-1.ps

9. Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 531–543. Springer, Heidelberg (2004)

   Chapter  Google Scholar 

10. Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: Graph distances in the streaming model: The value of space. Proc. 16th ACM-SIAM Symposium on Discrete Algorithms (2005)

    Google Scholar 

11. Munro, J., Paterson, M.: Selection and sorting with limited storage. Theoretical Computer Science 12, 315–323 (1980)

    Article  MATH  MathSciNet  Google Scholar 

12. Henzinger, M.R., Raghavan, P., Rajagopalan, S.: Computing on data streams. Technical Report 1998-001, DEC Systems Research Center (1998)

    Google Scholar 

13. Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. Journal of Computer and System Sciences 58, 137–147 (1999)

    Article  MATH  MathSciNet  Google Scholar 

14. Feigenbaum, J., Kannan, S., Strauss, M., Viswanathan, M.: An approximate L1 difference algorithm for massive data streams. SIAM Journal on Computing 32, 131–151 (2002)

    Article  MATH  MathSciNet  Google Scholar 

15. Guha, S., Mishra, N., Motwani, R., O’Callaghan, L.: Clustering data streams. In: Proc. 41th IEEE Symposium on Foundations of Computer Science, pp. 359–366 (2000)

    Google Scholar 

16. Drineas, P., Kannan, R.: Pass efficient algorithms for approximating large matrices. In: Proc. 14th ACM-SIAM Symposium on Discrete Algorithms, pp. 223–232 (2003)

    Google Scholar 

17. Buchsbaum, A.L., Giancarlo, R., Westbrook, J.: On finding common neighborhoods in massive graphs. Theor. Comput. Sci. 1-3, 707–718 (2003)

    Article  MathSciNet  Google Scholar 

Download references