Spanning adjacency oracles in sublinear time
From MaRDI portal
Cites work
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- A local algorithm for constructing spanners in minor-free graphs
- A Local Computation Approximation Scheme to Maximum Matching
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- A trade-off between space and efficiency for routing tables
- An Optimal Synchronizer for the Hypercube
- Best of two local models: centralized local and distributed local algorithms
- Can we locally compute sparse connected subgraphs?
- Constant-time local computation algorithms
- Constructing near spanning trees with few local inspections
- Converting online algorithms to local computation algorithms
- Graph spanners: a tutorial review
- scientific article; zbMATH DE number 7075933 (Why is no real title available?)
- scientific article; zbMATH DE number 7376014 (Why is no real title available?)
- scientific article; zbMATH DE number 3258067 (Why is no real title available?)
- scientific article; zbMATH DE number 7788381 (Why is no real title available?)
- Improved constant-time approximation algorithms for maximum matchings and other optimization problems
- Local algorithms for sparse spanning graphs
- Local computation algorithms for spanners
- Local Graph Partitions for Approximation and Testing
- Maintaining discrete probability distributions optimally
- New techniques and tighter bounds for local computation algorithms
- On sparse spanners of weighted graphs
- Random k-out subgraph leaves only O(n/k) inter-component edges
- Space-efficient local computation algorithms
This page was built for publication: Spanning adjacency oracles in sublinear time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6906420)
