Finding Large Independent Sets in Line of Sight Networks

DOI10.1007/978-3-319-53007-9_29zbMath1436.68259OpenAlexW2583658936MaRDI QIDQ2971663

Pavan Sangha, Michele Zito

Publication date: 7 April 2017

Published in: Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-53007-9_29

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Wireless sensor networks as related to computer science (68M18)

Related Items (2)

Independent Sets in Restricted Line of Sight Networks ⋮ Induced Embeddings into Hamming Graphs.

Cites Work

• On the efficiency of polynomial time approximation schemes
• Unit disk graphs
• Algorithms for drawing graphs: An annotated bibliography
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Gridline graphs: A review in two dimensions and an extension to higher dimensions
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• Line-of-Sight Networks
• Universality considerations in VLSI circuits
• Simple heuristics for unit disk graphs
• Graph-Theoretic Concepts in Computer Science
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Finding Large Independent Sets in Line of Sight Networks