Low diameter graph decompositions
type: Item
instance of: scholarly article
title: Low diameter graph decompositions
zbMATH Open document ID: 0790.05067
DOI: 10.1007/BF01303516
author: Nathan Linial
author: Michael Saks
published in: Combinatorica
publication date: 1994-06-22T00:00:00Z
review text: A preliminary version of this paper appeared as ``Decomposing graphs into regions of small diameter'' in Proc. 2nd ACM-SIAM Symposium on Discrete Algorithms, 320-330 (1991; Zbl 0785.05073).
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 522715
zbMATH Keywords: decomposition
zbMATH Keywords: blocks
zbMATH Keywords: diameter
zbMATH Keywords: distributed computations
zbMATH Keywords: distributed algorithm
zbMATH Keywords: Sperner's lemma
zbMATH Keywords: Tucker's lemma
MaRDI profile type: Publication
cites work: A fast and simple randomized parallel algorithm for the maximal independent set problem
cites work: Complexity of network synchronization
cites work: Q3896960
cites work: A constructive proof of Tucker's combinatorial lemma
cites work: The Game of Hex and the Brouwer Fixed-Point Theorem
cites work: Parallel Symmetry-Breaking in Sparse Graphs
cites work: Locality in Distributed Graph Algorithms
cites work: A Simple Parallel Algorithm for the Maximal Independent Set Problem
cites work: Q5522742
cites work: The computation of fixed points and applications
cites work: A combinatorial proof of the Borsuk-Ulam antipodal point theorem
full work available at URL: https://doi.org/10.1007/bf01303516
OpenAlex ID: W1998544343
Recommended article: Q5875752
Recommended article: Decompositions into Subgraphs of Small Diameter
Recommended article: Low-diameter graph decomposition is in NC
Recommended article: Q3138968
Recommended article: The decomposition dimension of graphs
Recommended article: Decomposition of graphs with constraint on minimum degree
Recommended article: Decomposing large graphs with small graphs of high density
Recommended article: Q3059009
description: scientific article; zbMATH DE number 522715