Approximation and Online Algorithms
From MaRDI portal
Publication:5898481
DOI10.1007/11671411zbMath1177.68258MaRDI QIDQ5898481
Publication date: 12 February 2007
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11671411
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68W25: Approximation algorithms
Related Items
Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes, Domination in Geometric Intersection Graphs, A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs, Shifting strategy for geometric graphs without geometry, The within-strip discrete unit disk cover problem, On pseudo-disk hypergraphs, Node-weighted Steiner tree approximation in unit disk graphs, Approximating minimum independent dominating sets in wireless networks, A randomized algorithm for determining dominating sets in graphs of maximum degree five, Impact of locality on location aware unit disk graphs, The \(k\)-hop connected dominating set problem: approximation and hardness, A PTAS for minimum \(d\)-hop connected dominating set in growth-bounded graphs, Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes, Liar's domination in unit disk graphs, On the approximability and hardness of the minimum connected dominating set with routing cost constraint, Polynomial-time approximation schemes for piercing and covering with applications in wireless networks, The number of disk graphs, Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs
