Local approximation schemes for ad hoc and sensor networks

No abstract is available for this paper.

• Publication year

  2005

• Venue

  DIALM-POMC '05

• Publication date

  2005-09-02

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1080810.1080827
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking

  2018cited by this paper
• Energy-Efficient, Collision-Free Medium Access Control for Wireless Sensor Networks

  2006cited by this paper
• The price of being near-sighted

  2006cited by this paper
• Distributed low-cost backbone formation for wireless ad hoc networks

  2005cited by this paper
• On the locality of bounded growth

  2005influential reference
• Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs

  2005influential reference
• Name independent routing for growth bounded networks

  2005cited by this paper
• On the node-scheduling approach to topology control in ad hoc networks

  2005cited by this paper
• A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs

  2005influential reference
• Maximal independent sets in radio networks

  2005cited by this paper
• Distributed Algorithms for Coloring and Domination in Wireless Ad Hoc Networks

  2004cited by this paper
• Wireless communication graphs

  2004cited by this paper
• Unit disk graph approximation

  2004influential reference
• A robust PTAS for maximum independent sets in unit disk graphs

  2004influential reference
• A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs

  2004influential reference
• Initializing newly deployed ad hoc and sensor networks

  2004cited by this paper
• A polynomial‐time approximation scheme for the minimum‐connected dominating set in ad hoc wireless networks

  2003cited by this paper
• Energy-efficient collision-free medium access control for wireless sensor networks

  2003cited by this paper
• Ad hoc networks beyond unit disk graphs

  2003cited by this paper
• New distributed algorithm for connected dominating set in wireless ad hoc networks

  2002cited by this paper
• Finding nearest neighbors in growth-restricted metrics

  2002cited by this paper
• Message-optimal connected dominating sets in mobile ad hoc networks

  2002cited by this paper
• Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks

  2002cited by this paper
• An efficient distributed algorithm for constructing small dominating sets

  2002cited by this paper
• Polynomial-time approximation schemes for geometric graphs

  2001cited by this paper
• Enhancing ad hoc routing with dynamic virtual infrastructures

  2001cited by this paper
• On calculating connected dominating set for efficient routing in ad hoc wireless networks

  1999cited by this paper
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs

  1998cited by this paper
• Unit disk graph recognition is NP-hard

  1998cited by this paper
• Global optimization using local information with applications to flow control

  1997cited by this paper
• A Unified Approach to Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs

  1994cited by this paper
• Simple heuristics for unit disk graphs

  1994cited by this paper
• Scheduling algorithms for multi-hop radio networks

  1992cited by this paper
• Unit disk graphs

  1991cited by this paper
• Approximation schemes for covering and packing problems in image processing and VLSI

  1985cited by this paper
• Complexity of network synchronization

  1985cited by this paper
• Approximation Schemes for Covering and Packing Problems in Robotics and VLSI

  1984cited by this paper
• Approximation algorithms for NP-complete problems on planar graphs

  1983cited by this paper
• Proceedings of the 33rd Hawaii International Conference on System Sciences- 2000 Energy-Efficient Communication Protocol for Wireless Microsensor Networks

  year unknowncited by this paper
• Constant Time Distributed Dominating Set Approximation

  year unknowncited by this paper

• A QPTAS for Facility Location on Unit Disk graphs

  2024cites this paper
• Low-Distortion Clustering in Bounded Growth Graphs

  2024cites this paper
• Coresets for Clustering in Geometric Intersection Graphs

  2023cites this paper
• Group Members

  2021cites this paper
• Bibliography of distributed approximation beyond bounded degree

  2020cites this paper
• Bibliography of distributed approximation on structurally sparse graph classes

  2020cites this paper
• When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time

  2019cites this paper
• An Efficient Local Search for the Minimum Independent Dominating Set Problem

  2018cites this paper
• Adversarial Input in Games and Markets

  2016cites this paper
• Distributed Approximation Algorithms for Spectrum Allocation in Wireless ad Hoc Networks

  2016influential citation
• The power of frequency hopping and information dissemination in constrained communication models

  2015cites this paper
• Semi-asynchronous and distributed weighted connected dominating set algorithms for wireless sensor networks

  2015cites this paper
• PTAS for Minimum k-Path Connected Vertex Cover in Growth-Bounded Graphs

  2014cites this paper
• Network connectivity maintenance of WSNs in node failure-prone environment: A detailed survey

  2014cites this paper
• L ABounds on Contention Management in Radio Networks

  2013cites this paper
• Solving the Minimum Independent Domination Set Problem in Graphs by Exact Algorithm and Greedy Heuristic

  2013cites this paper
• Méthodes exactes et approchées par partition en cliques de graphes. (Exact and approximation methods by clique partition of graphs)

  2013cites this paper
• Shifting strategy for geometric graphs without geometry

  2012cites this paper
• Approximating node-weighted Steiner subgraphs for multicast communication in wireless networks

  2012cites this paper
• Distributed algorithms for sensor networks

  2012cites this paper
• Distributed Coverage in Wireless Ad Hoc and Sensor Networks by Topological Graph Approaches

  2012cites this paper
• Bounds on Contention Management in Radio Networks

  2012cites this paper
• Good Quality Virtual Realization of Unit Disk Graphs

  2011cites this paper
• Edge Self-Monitoring for Wireless Sensor Networks

  2011cites this paper
• A framework for the design of systems with intelligent and interactive information flow

  2010cites this paper
• A new technique for distributed symmetry breaking

  2010cites this paper
• Fast Distributed Approximation Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs

  2009cites this paper
• Low complexity stable link scheduling for maximizing throughput in wireless networks

  2009cites this paper
• Shifting strategy for geometric graphs without geometry

  2009cites this paper
• Scheduling in Multi-Hop Wireless Networks with Priorities

  2009cites this paper
• UvA-DARE ( Digital Academic Repository ) Optimization and approximation on systems of geometric objects

  2009cites this paper
• Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs

  2009cites this paper
• A PTAS for Minimum Clique Partition in Unit Disk Graphs

  2009influential citation
• Algorithmic Models of Interference in Wireless Ad Hoc and Sensor Networks

  2009cites this paper
• A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs

  2009influential citation
• Connected Dominating Sets

  2009cites this paper
• Coloring unstructured wireless multi-hop networks

  2009cites this paper
• Locating sinks in wireless sensor networks

  2009cites this paper
• Algorithmic solutions for transient faults in communication networks

  2009cites this paper
• Construction of virtual backbone on growth-bounded graph with variable transmission range

  2008cites this paper
• Distributed packing in planar graphs

  2008cites this paper
• Closing the complexity gap between FCFS mutual exclusion and mutual exclusion

  2008cites this paper
• Constructing Distributed Connected Dominating Sets in Growth-Bounded Graphs

  2008cites this paper
• Sensor Networks Continue to Puzzle: Selected Open Problems

  2008cites this paper
• Impact of Locality on Location Aware Unit Disk Graphs

  2008cites this paper
• Fast Distributed Approximations in Planar Graphs

  2008cites this paper
• Low Complexity Stable Link Scheduling for Maximizing Throughput in Multihop Wireless Networks

  2008cites this paper
• Arbitrary Throughput Versus Complexity Tradeoffs in Wireless Networks Using Graph Partitioning

  2008cites this paper
• Energy efficient data gathering in sensor networks

  2008cites this paper
• ALGORITHMIC MODELS FOR SENSOR NETWORKS Seminar work of

  2008cites this paper
• Local 3-approximation algorithms for weighted dominating set and vertex cover in quasi unit-disk graphs

  2008cites this paper
• Local Maximal Matching and Local 2-Approximation for Vertex Cover in UDGs

  2008cites this paper
• A log-star distributed maximal independent set algorithm for growth-bounded graphs

  2008cites this paper
• Local PTAS for Independent Set and Vertex Cover in Location Aware Unit Disk Graphs?

  2008cites this paper
• On locality and related problems: Communicating, computing, exploring

  2008cites this paper
• Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes

  2008cites this paper
• Construction of distributed connected dominating sets in growth-bounded graphs

  2008cites this paper
• Local Approximation of Covering and Packing Problems

  2008cites this paper
• Modeling Sensor Networks

  2008cites this paper
• Connected Dominating Sets

  2007cites this paper
• LOCAL PTAS FOR DOMINATING AND CONNECTED DOMINATING SET IN LOCATION AWARE UDGS

  2007cites this paper
• Good Quality Virtual Realization of Unit Ball Graphs

  2007cites this paper
• Distributed Approximations for Packing in Unit-Disk Graphs

  2007cites this paper
• A Faster Distributed Approximation Scheme for the Connected Dominating Set Problem for Growth-Bounded Graphs

  2007influential citation
• Composition of the Graduation Committee

  2007cites this paper
• Scalable Load-Distance Balancing

  2007cites this paper
• A distributed approximation scheme for sleep sceduling in sensor networks

  2007cites this paper
• Distributed algorithms for weighted problems in minor-closed families

  2007cites this paper
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs

  2007cites this paper
• Coordinating Concurrent Transmissions: A Constant-Factor Approximation of Maximum-Weight Independent Set in Local Conflict Graphs

  2007cites this paper
• Local Approximation Algorithms for Scheduling Problems in Sensor Networks

  2007cites this paper
• Geometric Approaches to Ad Hoc and Sensor Networks: Full Report of the 2006 NSF Workshop

  2006cites this paper
• Exact Algorithms for Finding the Minimum Independent Dominating Set in Graphs

  2006cites this paper
• Distributed Approximation Algorithms in Unit-Disk Graphs

  2006cites this paper
• Independent and dominating sets in wireless communication graphs

  2006cites this paper
• Algorithmic models for sensor networks

  2006cites this paper
• Understanding ad hoc networks: from geometry to mobility

  2006cites this paper
• Distributed Almost Exact Approximations for Minor-Closed Families

  2006cites this paper
• The price of locality: exploring the complexity of distributed coordination primitives

  2005cites this paper
• Ad hoc networks beyond unit disk graphs

  2003cites this paper
• Scalable Load-Distance Balancing 1

  year unknowncites this paper