×

zbMATH — the first resource for mathematics

Local-global phenomena in graphs. (English) Zbl 0803.68085
Summary: This is a survey of a number of recent papers dealing with graphs from a geometric perspective. The main theme of these studies in 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.

MSC:
68R10 Graph theory (including graph drawing) in computer science
68W15 Distributed algorithms
05C90 Applications of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] DOI: 10.1137/0221015 · Zbl 0787.05058 · doi:10.1137/0221015
[2] Linial, ISTCS
[3] DOI: 10.1145/4221.4226 · Zbl 0633.68026 · doi:10.1145/4221.4226
[4] Blum, FOCS 31 pp 554– (1990)
[5] DOI: 10.1016/0095-8956(90)90026-V · Zbl 0708.05032 · doi:10.1016/0095-8956(90)90026-V
[6] Awerbuch, FOCS 31 pp 514– (1990)
[7] Awerbuch, FOCS 31 pp 503– (1990)
[8] Awerbuch, STOC 24 pp 571– (1992)
[9] DOI: 10.1145/2157.2158 · Zbl 0627.68057 · doi:10.1145/2157.2158
[10] Awerbuch, FOCS 30 pp 364– (1989)
[11] Szegedy, STOC 25 (1993)
[12] Awerbuch, PODC 11 pp 169– (1992)
[13] DOI: 10.1016/S0304-0208(08)70288-3 · doi:10.1016/S0304-0208(08)70288-3
[14] Alon, FOCS 33 pp 334– (1992)
[15] Stein, Annals of Math. Study 63 (1970)
[16] DOI: 10.1016/0196-6774(86)90019-2 · Zbl 0631.68063 · doi:10.1016/0196-6774(86)90019-2
[17] Naor, STOC 25 (1993)
[18] DOI: 10.1137/0404036 · Zbl 0738.68007 · doi:10.1137/0404036
[19] Hurewicz, Dimension Theory (1948)
[20] Graham, Ramsey Theory (1980)
[21] Garey, Computers and Intractability: A Guide to NP-completeness (1979) · Zbl 0411.68039
[22] Gallai, Publ. Math. Inst. Hungar. Acad. Set 8 pp 165– (1963)
[23] DOI: 10.1016/0021-8693(64)90028-6 · Zbl 0126.05303 · doi:10.1016/0021-8693(64)90028-6
[24] Erdös, Canad. J. Math. 14 pp 702– (1962) · Zbl 0194.25304 · doi:10.4153/CJM-1962-060-4
[25] Erdös, Mat. Lapok 11 pp 264– (1960)
[26] Cole, STOC 18 pp 206– (1986)
[27] DOI: 10.1016/0012-365X(91)90042-Z · Zbl 0767.05083 · doi:10.1016/0012-365X(91)90042-Z
[28] Motwani, Computing roots of graphs is hard (1991) · Zbl 0812.68103
[29] DOI: 10.1137/0215074 · Zbl 0619.68058 · doi:10.1137/0215074
[30] DOI: 10.1007/BF02126799 · Zbl 0661.05035 · doi:10.1007/BF02126799
[31] Linial, Combinatorica.
[32] Linial, J. Combin. Th.
[33] Khanna, ISTCS
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.