Approximation and Online Algorithms
From MaRDI portal
Publication:5898481
DOI10.1007/11671411zbMath1177.68258OpenAlexW4210634114MaRDI 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
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Related Items (25)
On pseudo-disk hypergraphs ⋮ On dominating set of some subclasses of string graphs ⋮ Node-weighted Steiner tree approximation in unit disk graphs ⋮ Parallel algorithm for minimum partial dominating set in unit disk graph ⋮ A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph ⋮ Impact of locality on location aware unit disk graphs ⋮ The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph ⋮ Algorithmic aspects of secure domination in unit disk graphs ⋮ A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs ⋮ Liar's domination in unit disk graphs ⋮ A PTAS for minimum \(d\)-hop connected dominating set in growth-bounded graphs ⋮ Shifting strategy for geometric graphs without geometry ⋮ Polynomial-time approximation schemes for piercing and covering with applications in wireless networks ⋮ The within-strip discrete unit disk cover problem ⋮ Vertex-edge domination in unit disk graphs ⋮ Approximating minimum independent dominating sets in wireless networks ⋮ Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes ⋮ Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs ⋮ The number of disk graphs ⋮ Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes ⋮ Domination in Geometric Intersection Graphs ⋮ Upper and lower bounds on approximating weighted mixed domination ⋮ A randomized algorithm for determining dominating sets in graphs of maximum degree five ⋮ On the approximability and hardness of the minimum connected dominating set with routing cost constraint
This page was built for publication: Approximation and Online Algorithms
