Low diameter graph decompositions

DOI10.1007/BF01303516zbMath0790.05067OpenAlexW1998544343MaRDI 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

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12) Distributed algorithms (68W15)

Related Items

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

Cites Work