Local-Global Phenomena in Graphs

DOI10.1017/S0963548300000857MaRDI QIDQ4290099zbMATH OpenOpenAlexFDO

Authors 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

distributed computingmaximal functionscoveringpackinglocal 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)

Recommendations

• scientific article; zbMATH DE number 1047739
• scientific article; zbMATH DE number 91024
• scientific article; zbMATH DE number 3902710
• Survey of local algorithms
• Local properties of geometric graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A fast parallel algorithm for the maximal independent set problem
• Computing roots of graphs is hard
• Graphs without large triangle free subgraphs
• Improving the performance guarantee for approximate graph coloring
• Locality in Distributed Graph Algorithms
• Note on the girth of Ramanujan graphs
• Ramanujan graphs
• The Construction of Certain Graphs
• The nonexistence of certain generalized polygons

Cited in

(11)

• What Does the Local Structure of a Planar Graph Tell Us About Its Global Structure?
• On a local similarity of graphs
• Reconstructing trees from digitally convex sets
• The geometry of graphs and some of its algorithmic applications
• Local properties of geometric graphs
• Tree-depth, subgraph coloring and homomorphism bounds
• Some local-global phenomena in locally finite graphs
• Large cliques and independent sets all over the place
• Performance analysis of distance-1 distributed algorithms for admission control under the 2-hop interference model
• Local dependency in networks
• Localization of edges in graph models of two-level algorithms

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4290099)