Local Algorithms for Sparse Spanning Graphs
Abstract Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider a relaxed version of this problem in the setting of local algorithms. The relaxation is that the constructed subgraph is a sparse spanning subgraph containing at most $$(1+\epsilon )n$$(1+ϵ)...
| Main Authors: | , , |
|---|---|
| Andre forfattere: | |
| Format: | Article |
| Sprog: | English |
| Udgivet: |
Springer US
2021
|
| Online adgang: | https://hdl.handle.net/1721.1/131506 |