Local-Global Phenomena in Graphs

DOI10.1017/S0963548300000857zbMATH Open0803.68085OpenAlexW2064812011MaRDI QIDQ4290099FDOQ4290099

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

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

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)

Cites Work

• Title not available (Why is that?)
• The nonexistence of certain generalized polygons
• Computing roots of graphs is hard
• Ramanujan graphs
• 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
• Locality in Distributed Graph Algorithms
• Improving the performance guarantee for approximate graph coloring
• Graphs without large triangle free subgraphs
• The Construction of Certain Graphs
• Note on the girth of Ramanujan graphs
• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring

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)