Near-Linear Time Construction of Sparse Neighborhood Covers

DOI10.1137/S0097539794271898zbMATH Open0943.05079MaRDI QIDQ4210147FDOQ4210147

Authors: Baruch Awerbuch, Bonnie Berger, Lenore J. Cowen, David Peleg 

Publication date: 21 September 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Recommendations

• Fast distributed network decompositions and covers
• Sparse covers for planar graphs and graphs that exclude a fixed minor
• Fast network decomposition
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t

zbMATH Keywords

spannersapproximate shortest pathsnetwork decompositionsneighborhood cover

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (only showing first 100 items - show all)

• Matching triangles and basing hardness on an extremely popular conjecture
• Generating sparse 2—spanners
• Spectral sparsification and regret minimization beyond matrix multiplicative updates
• A polynomial-time bicriteria approximation scheme for planar bisection
• Polynomially low error PCPs with \(\operatorname{polyloglog} n\) queries via modular composition
• Almost Optimal Pseudorandom Generators for Spherical Caps
• \(\ell_p\) row sampling by Lewis weights
• A characterization of the capacity of online (causal) binary channels
• Time lower bounds for nonadaptive turnstile streaming algorithms
• Analysis of a classical matrix preconditioning algorithm
• Reed-Muller codes for random erasures and errors
• A Directed Isoperimetric Inequality with application to Bregman Near Neighbor Lower Bounds
• The List Decoding Radius of Reed-Muller Codes over Small Fields
• The communication complexity of interleaved group products
• Compact roundtrip routing with topology-independent node names
• FPTAS for \#BIS with degree bounds on one side
• Deterministic global minimum cut of a simple graph in near-linear time
• Sparse covers for planar graphs and graphs that exclude a fixed minor
• Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
• A new deterministic algorithm for fully dynamic all-pairs shortest paths
• Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
• Prioritized metric structures and embedding
• Faster algorithms for all-pairs small stretch distances in weighted graphs
• On the Lovász theta function for independent sets in sparse graphs
• Efficiently learning Ising models on arbitrary graphs (extended abstract)
• Sparse quantum codes from quantum circuits
• Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs
• Beyond the Euler characteristic: approximating the genus of general graphs (extended abstract)
• Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs
• Preserving statistical validity in adaptive data analysis (extended abstract)
• Fast deterministic distributed algorithms for sparse spanners
• Random permutations using switching networks
• Randomized composable core-sets for distributed submodular maximization
• The Power of Dynamic Distance Oracles
• Dictionary learning and tensor decomposition via the sum-of-squares method
• Small value parallel repetition for general games
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Nearly-linear time positive LP solver with faster convergence rate
• Inapproximability of Nash equilibrium
• Sketching and embedding are equivalent for norms
• Minimizing flow-time on unrelated machines
• Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
• From independence to expansion and back again
• A parallel bio-inspired shortest path algorithm
• Test-and-set in optimal space
• Dimensionality reduction for \(k\)-means clustering and low rank approximation
• Adjacency labeling schemes and induced-universal graphs
• Non-malleable reductions and applications
• Learning mixtures of Gaussians in high dimensions
• Approximate \(k\)-flat nearest neighbor search
• Optimal data-dependent hashing for approximate near neighbors
• Randomized rounding for the largest simplex problem
• Approximate distance oracles with improved bounds
• The directed grid theorem
• Testing cluster structure of graphs
• Byzantine agreement with optimal early stopping, optimal resilience and polynomial complexity
• Succinct randomized encodings and their applications
• On the complexity of Nash equilibria in anonymous games
• All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time
• Indistinguishability obfuscation for Turing machines with unbounded memory
• Succinct garbling and indistinguishability obfuscation for RAM programs
• Garbled RAM from one-way functions
• Quantum information complexity
• Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions
• 2-server PIR with sub-polynomial communication
• Computing with Tangles
• Secretary Problems with Non-Uniform Arrival Order
• Ramsey partitions and proximity data structures
• Forrelation: a problem that optimally separates quantum from classical computing
• Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
• Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
• An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
• Sublinear fully distributed partition with applications
• Leveled fully homomorphic signatures from standard lattices
• How well can graphs represent wireless interference?
• The complexity of the simplex method
• Super-resolution, extremal functions and the condition number of Vandermonde matrices
• Online submodular welfare maximization: greedy beats 1/2 in random order
• Hardness of Graph Pricing Through Generalized Max-Dicut
• Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
• Shortest-path queries in static networks
• Local, private, efficient protocols for succinct histograms
• Quantum spectrum testing
• High Parallel Complexity Graphs and Memory-Hard Functions
• Edge-disjoint spanners of complete graphs and complete digraphs
• Greedy algorithms for Steiner forest
• Fast matrix multiplication: limitations of the Coppersmith-Winograd method (extended abstract)
• Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
• Bypassing KLS: Gaussian cooling and an \(O^\ast(n^3)\) volume algorithm
• Faster canonical forms for primitive coherent configurations (extended abstract)
• Solving the shortest vector problem in \(2^n\) time using discrete Gaussian sampling (extended abstract)
• Excluded grid theorem: improved and simplified
• Learning Arbitrary Statistical Mixtures of Discrete Distributions
• Tight bounds for learning a mixture of two Gaussians (extended abstract)
• Exponential Separation of Information and Communication for Boolean Functions
• Rectangles Are Nonnegative Juntas
• Toward a unified theory of sparse dimensionality reduction in Euclidean space
• Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Carathéodory's theorem
• Approximating the Nash social welfare with indivisible items
• Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization

This page was built for publication: Near-Linear Time Construction of Sparse Neighborhood Covers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210147)