Low diameter graph decompositions

DOI10.1007/BF01303516zbMath0790.05067MaRDI QIDQ1316650

Publication date: 22 June 1994

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01303516

zbMATH Keywords

decomposition; diameter; blocks; Sperner's lemma; distributed algorithm; distributed computations; Tucker's lemma

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C15: Coloring of graphs and hypergraphs

05C12: Distance in graphs

68W15: Distributed algorithms

Related Items

Unnamed Item, Decompositions into Subgraphs of Small Diameter, Distributed Spanner Approximation, Network Decomposition and Distributed Derandomization (Invited Paper), Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering, Graph Clustering using Effective Resistance, Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs, Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs, Subexponential parameterized algorithms for graphs of polynomial growth, Euclidean distortion and the sparsest cut, The Local and Global Price of Anarchy of Graphical Games, Colouring Planar Graphs With Three Colours and No Large Monochromatic Components, Cutting Corners Cheaply, or How to Remove Steiner Points, Unnamed Item, The intrinsic dimensionality of graphs, Improved distributed algorithms for coloring interval graphs with application to multicoloring trees, Distributed deterministic edge coloring using bounded neighborhood independence, Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering, On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition, An approximation algorithm for clustering graphs with dominating diametral path, Distributed approximation of capacitated dominating sets, Local and global price of anarchy of graphical games, Distributed algorithms for covering, packing and maximum weighted matching, About randomised distributed graph colouring and graph partition algorithms, Random martingales and localization of maximal inequalities, Volume distortion for subsets of Euclidean spaces, Short paths in $\varepsilon $-regular pairs and small diameter decompositions of dense graphs, Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms, Simple and efficient network decomposition and synchronization, A fast network-decomposition algorithm and its applications to constant-time distributed computation, Extending Lipschitz functions via random metric partitions, Absolute Lipschitz extendability, Light spanners for high dimensional norms via stochastic decompositions, No sublogarithmic-time approximation scheme for bipartite vertex cover, Set cover problems with small neighborhood covers, Fréchet embeddings of negative type metrics, Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons, Distributed strong diameter network decomposition, Distributed minimum vertex coloring and maximum independent set in chordal graphs, Distributed Distance-Bounded Network Design Through Distributed Convex Programming, A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation, Large Monochromatic Components in Two-colored Grids, Graph coloring with no large monochromatic components, Deciding Relaxed Two-Colourability: A Hardness Jump

Cites Work