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

coveringdistributed computinglocal structural informationlocality of computationmaximal functionspacking

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

• 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
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Computing roots of graphs is hard
• Graphs without large triangle free subgraphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 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

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)