Local planar domination revisited

DOI10.1007/978-3-031-09993-9_9OpenAlexW3215175533MaRDI QIDQ2097345

Sebastian Siebertz, Alexandre Vigny, Ozan Heydt

Publication date: 11 November 2022

Full work available at URL: https://arxiv.org/abs/2111.14506

zbMATH Keywords

planar graphsdominating setLOCAL algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)

Related Items (1)

Brief Announcement: Local Problems in the SUPPORTED Model

Cites Work

• Kernelization using structural parameters on sparse graph classes
• Distributed minimum dominating set approximations in restricted families of graphs
• Sparsity. Graphs, structures, and algorithms
• Connected dominating set. Theory and applications
• Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
• On the maximum number of cliques in a graph
• Tight approximation bounds for dominating set on graphs of bounded arboricity
• Greedy domination on biclique-free graphs
• Constant round distributed domination on graph classes with bounded expansion
• A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
• On the degrees of the vertices of a directed graph
• Survey of local algorithms
• Local Computation
• The price of being near-sighted
• Distributed Dominating Set Approximations beyond Planar Graphs
• Reducibility among Combinatorial Problems
• On distance ‐dominating and ‐independent sets in sparse graphs

This page was built for publication: Local planar domination revisited