Finding Large Independent Sets in Line of Sight Networks

DOI10.1007/978-3-319-53007-9_29zbMATH Open1436.68259OpenAlexW2583658936MaRDI QIDQ2971663FDOQ2971663

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) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Wireless sensor networks as related to computer science (68M18)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Unit disk graphs
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Graphs on surfaces
• Algorithms for drawing graphs: An annotated bibliography
• On the efficiency of polynomial time approximation schemes
• 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
• Universality considerations in VLSI circuits
• Simple heuristics for unit disk graphs
• Graph-Theoretic Concepts in Computer Science
• Line-of-Sight Networks
• Gridline graphs: A review in two dimensions and an extension to higher dimensions

Cited In (3)

• Independent Sets in Restricted Line of Sight Networks
• Induced Embeddings into Hamming Graphs.
• Vertex-connectivity for node failure identification in Boolean network tomography

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

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