Local-Global Phenomena in Graphs

DOI10.1017/S0963548300000857zbMath0803.68085OpenAlexW2064812011MaRDI QIDQ4290099

Nathan Linial

Publication date: 28 April 1994

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548300000857

zbMATH Keywords

coveringpackingmaximal functionsdistributed computinglocal structural informationlocality of computation

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items (6)

The geometry of graphs and some of its algorithmic applications ⋮ Reconstructing trees from digitally convex sets ⋮ Some local-global phenomena in locally finite graphs ⋮ Performance analysis of distance-1 distributed algorithms for admission control under the 2-hop interference model ⋮ Tree-depth, subgraph coloring and homomorphism bounds ⋮ Large cliques and independent sets all over the place

Cites Work

• Unnamed Item
• Note on the girth of Ramanujan graphs
• Ramanujan graphs
• Graphs without large triangle free subgraphs
• Computing roots of graphs is hard
• The nonexistence of certain generalized polygons
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Improving the performance guarantee for approximate graph coloring
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A fast parallel algorithm for the maximal independent set problem
• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
• Locality in Distributed Graph Algorithms
• The Construction of Certain Graphs

This page was built for publication: Local-Global Phenomena in Graphs