Fast Distributed Approximations in Planar Graphs

DOI10.1007/978-3-540-87779-0_6zbMath1161.68865OpenAlexW1869515244MaRDI QIDQ3540222

Wojciech Wawrzyniak, Michał Hanćkowiak, Andrzej Czygrinow

Publication date: 20 November 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-87779-0_6

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (39)

Node labels in local decision ⋮ Distributed independent sets in interval and segment intersection graphs ⋮ Distributed distance domination in graphs with no \(K_{2,t}\)-minor ⋮ Exact Bounds for Distributed Graph Colouring ⋮ Distributed minimum dominating set approximations in restricted families of graphs ⋮ Property testing of planarity in the \textsf{CONGEST} model ⋮ Distributed minimum vertex coloring and maximum independent set in chordal graphs ⋮ Deterministic Massively Parallel Connectivity ⋮ Linear-in-\(\varDelta \) lower bounds in the LOCAL model ⋮ The energy complexity of diameter and minimum cut computation in bounded-genus networks ⋮ The energy complexity of diameter and minimum cut computation in bounded-genus networks ⋮ Computing large independent sets in a single round ⋮ 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 ⋮ Brief Announcement: Local Problems in the SUPPORTED Model ⋮ Analysing local algorithms in location-aware quasi-unit-disk graphs ⋮ Distributed \(\mathcal{CONGEST}_{B C}\) constant approximation of MDS in bounded genus graphs ⋮ Almost stable matchings by truncating the Gale-Shapley algorithm ⋮ A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs ⋮ Leveraging Linial’s Locality Limit ⋮ Distributed algorithms for covering, packing and maximum weighted matching ⋮ Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs ⋮ Local approximability of max-min and min-max linear programs ⋮ No sublogarithmic-time approximation scheme for bipartite vertex cover ⋮ A simple local 3-approximation algorithm for vertex cover ⋮ Best of two local models: centralized local and distributed local algorithms ⋮ An optimal maximal independent set algorithm for bounded-independence graphs ⋮ Compact distributed certification of planar graphs ⋮ Local approximation of the maximum cut in regular graphs ⋮ Distributed approximation algorithms for \(k\)-dominating set in graphs of bounded genus and linklessly embeddable graphs ⋮ Weak models of distributed computing, with connections to modal logic ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs ⋮ A local approximation algorithm for minimum dominating set problem in anonymous planar networks ⋮ Distributed Dominating Set Approximations beyond Planar Graphs ⋮ Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs ⋮ Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs ⋮ Local certification of graphs with bounded genus ⋮ Constant round distributed domination on graph classes with bounded expansion

Cites Work

This page was built for publication: Fast Distributed Approximations in Planar Graphs