Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-25T00:28:06.730Z Has data issue: false hasContentIssue false
  • English
  • Français

Local-Global Phenomena in Graphs

Published online by Cambridge University Press:  12 September 2008

Nathan Linial
Nathan Linial
Affiliation:
Institute of Computer Science, Hebrew University, Jerusalem, Israel
Get access Rights & Permissions [Opens in a new window]

Abstract

This is a survey of a number of recent papers dealing with graphs from a geometric perspective. The main theme of these studies is the relationship between graph properties that are local in nature, and global graph parameters. Connections with the theory of distributed computing are pointed out and many open problems are presented.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 2 , Issue 4 , December 1993 , pp. 491 - 503
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Alon, N., Babai, L. and Itai, A. (1986) A fast and simple randomized algorithm for the maximal independent set problem. J. of Algorithms 7 567–583.CrossRefGoogle Scholar
[2]Alon, N., Kalai, G., Ricklin, M. and Stockmeyer, L. (1992) Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling. FOCS 33 334–343.Google Scholar
[3]Awerbuch, B., Berger, B., Cowen, L. and Peleg, D. (1992) Fast distributed network decomposition. PODC 11 169–178.Google Scholar
[4]Awerbuch, B., Goldberg, A. V., Luby, M. and Plotkin, S. A. (1989) Network decomposition and locality in distributed computation. FOCS 30 364–369.Google Scholar
[5]Awerbuch, B., Kutten, S. and Peleg, D. (1992) Competitive distributed job scheduling. STOC 24 571–580.Google Scholar
[6]Awerbuch, B. and Peleg, D. (1990) Sparse partitions. FOCS 31 503–513.Google Scholar
[7]Awerbuch, B. and Peleg, D. (1990) Network synchronization with polylogarithmic overhead. FOCS 31 514–522.Google Scholar
[8]Biggs, N. L. and Boshier, A. G. (1990) Note on the girth of Ramanujan graphs. J. Combin. Th. ser. B 49 190–194.CrossRefGoogle Scholar
[9]Blum, A. (1990) Some tools for approximate 3-coloring. FOCS 31 554–562.Google Scholar
[10]Bollobás, B. and Hind, H. R. (1991) Graphs without large triangle free subgraphs. Discrete Math. 87 119–131.CrossRefGoogle Scholar
[11]Cole, R. and Vishkin, U. (1986) Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. STOC 18 206–219.Google Scholar
[12]Erdös, P. and Gallai, T. (1960) Graphen mit Punkten vorgeschriebenen Grades. Mat. Lapok 11 264–274.Google Scholar
[13]Erdös, P. and Rogers, C. A. (1962) The construction of certain graphs. Canad. J. Math. 14 702–707.CrossRefGoogle Scholar
[14]Feit, W. and Higman, G. (1964) The nonexistence of certain generalized polygons. J. Algebra 1 114–131.CrossRefGoogle Scholar
[15]Gallai, T. (1963) Kritische Graphen I. Publ. Math. Inst. Hungar. Acad. Set 8 165–192.Google Scholar
[16]Garey, M. R. and Johnson, D. S. (1979) Computers and Intractability: A Guide to NP-completeness, W. H. Freeman.Google Scholar
[17]Graham, R. L., Rothschild, B. L. and Spencer, J. (1980) Ramsey Theory, Wiley, New York.Google Scholar
[18]Hoori, S. and Linial, N. (03 1993) Work in progress.Google Scholar
[19]Hurewicz, W. and Wallman, H. (1948) Dimension Theory, Princeton University Press.Google Scholar
[20]Karp, R. and Wigderson, A. (1985) A fast parallel algorithm for the maximal independent set problem. J. ACM 32 762–773.CrossRefGoogle Scholar
[21]Khanna, S., Linial, N. and Safra, S. (to appear) On the hardness of approximating the chromatic number. ISTCS.Google Scholar
[22]Linial, N. (1992) Locality in distributed graph algorithms. SIAM J. Comp. 21 193–201. (Preliminary version: Linial, N, (1987) Distributive graph algorithms – global solutions from local data. FOCS 331–335.CrossRefGoogle Scholar
[23]Linial, N., Peleg, D., Rabinovich, Yu. and Saks, M. (to appear) Sphere packing and local majorities in graphs. ISTCS.Google Scholar
[24]Linial, N. and Rabinovich, Yu. (in press) Local and global clique numbers. J. Combin. Th. ser. B.Google Scholar
[25]Linial, N. and Saks, M. (to appear) Low diameter graph decompositions. Combinatorica. (Preliminary version (1991) published in SODA 2 320–330.)Google Scholar
[26]Lubotsky, A., Phillips, R. and Sarnak, P. (1988) Ramanujan graphs. Combinatorica 8 261–278.CrossRefGoogle Scholar
[27]Luby, M. (1986) A simple parallel algorithm for the maximal independent set problem. S1AM J. Comp. 15 1036–1053.Google Scholar
[28]Lund, C. and Yanakakis, M. (1992) On the Hardness of Approximating Minimization Problems, manuscript.CrossRefGoogle Scholar
[29]Motwani, R. and Sudan, M. (1991) Computing roots of graphs is hard, manuscript Stanford.Google Scholar
[30]Naor, M. (1991) A lower bound on probabilistic algorithms for distributive ring coloring. SIAM J. Disc. Math. 4 409–412.CrossRefGoogle Scholar
[31]Naor, M. and Stockmeyer, L. (1993, to appear) What can be Computed Locally? STOC 25.Google Scholar
[32]Stein, E. M. (1970) Topics in Harmonic Analysis. Annals of Math. Study 63, Princeton University Press.Google Scholar
[33]Stein, E. M. (1985) Three variations on the theme of maximal functions. In: Peral, I. and Rubio de Francia, J.-L. (eds.) Recent Progress in Fourier Analysis, North-Holland Mathematics Studies 111, North-Holland, 229–244.Google Scholar
[34]Szegedy, M. and Vishwanatan, S. (1993, to appear) Locality-based graph coloring. STOC 25.Google Scholar
[35]Wigderson, A. (1983) Improving the performance for approximate graph coloring. J. ACM 30 325–329.CrossRefGoogle Scholar