Local planar domination revisited

DOI10.1007/978-3-031-09993-9_9MaRDI QIDQ2097345zbMATH OpenOpenAlexFDO

Authors Ozan Heydt, Sebastian Siebertz, Alexandre Vigny

Publication date 11 November 2022

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

zbMATH Keywords

dominating setplanar graphsLOCAL algorithms

Mathematics Subject Classification ID

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

Cites work

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

Cited in

(1)

• Brief Announcement: Local Problems in the SUPPORTED Model

This page was built for publication: Local planar domination revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2097345)