Fast Distributed Approximations in Planar Graphs
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 863494 (Why is no real title available?)
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- Deterministic coin tossing with applications to optimal parallel list ranking
- Distributed Almost Exact Approximations for Minor-Closed Families
- Distributed Approximation Algorithms for Planar Graphs
- Distributed Approximation Algorithms in Unit-Disk Graphs
- Distributed Computing
- Distributed Computing: A Locality-Sensitive Approach
- Distributed algorithms for weighted problems in sparse graphs
- Fast Distributed Algorithms Via Primal-Dual (Extended Abstract)
- Leveraging Linial’s Locality Limit
- Locality in Distributed Graph Algorithms
Cited in
(49)- An optimal maximal independent set algorithm for bounded-independence graphs
- Local certification of graphs with bounded genus
- Distributed independent sets in interval and segment intersection graphs
- Distributed algorithms for weighted problems in sparse graphs
- Weak models of distributed computing, with connections to modal logic
- Distributed distance-\(r\) covering problems on sparse high-girth graphs
- Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
- Distributed independent sets in interval and segment intersection graphs
- The energy complexity of diameter and minimum cut computation in bounded-genus networks
- Distributed approximation algorithms for k-dominating set in graphs of bounded genus and linklessly embeddable graphs
- A simple local 3-approximation algorithm for vertex cover
- Near-optimal distributed DFS in planar graphs
- Local approximation of the maximum cut in regular graphs
- Exact bounds for distributed graph colouring
- Distributed distance domination in graphs with no \(K_{2,t}\)-minor
- Leveraging Linial’s Locality Limit
- No sublogarithmic-time approximation scheme for bipartite vertex cover
- Compact distributed certification of planar graphs
- Best of two local models: centralized local and distributed local algorithms
- Improved distributed approximations for maximum independent set
- Distributed approximation for \(f\)-matching
- Distributed domination on sparse graph classes
- A local approximation algorithm for minimum dominating set problem in anonymous planar networks
- Property testing of planarity in the \textsf{CONGEST} model
- Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
- Almost stable matchings by truncating the Gale-Shapley algorithm
- The energy complexity of diameter and minimum cut computation in bounded-genus networks
- Distributed distance-r covering problems on sparse high-girth graphs
- A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
- Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
- Brief Announcement: Local Problems in the SUPPORTED Model
- The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
- Distributed minimum vertex coloring and maximum independent set in chordal graphs
- Distributed Dominating Set Approximations beyond Planar Graphs
- Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs
- scientific article; zbMATH DE number 2119743 (Why is no real title available?)
- Analysing local algorithms in location-aware quasi-unit-disk graphs
- Distributed minimum dominating set approximations in restricted families of graphs
- Local approximability of max-min and min-max linear programs
- Linear-in- lower bounds in the LOCAL model
- Distributed Approximation Algorithms for Planar Graphs
- Near-optimal distributed dominating set in bounded arboricity graphs
- Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
- The distributed complexity of locally checkable labeling problems beyond paths and trees
- Mobile agents on chordal graphs: maximum independent set and beyond
- Distributed algorithms for covering, packing and maximum weighted matching
- Computing large independent sets in a single round
- Distributed \(\mathcal{CONGEST}_{B C}\) constant approximation of MDS in bounded genus graphs
- Constant round distributed domination on graph classes with bounded expansion
This page was built for publication: Fast Distributed Approximations in Planar Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3540222)
