Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs

No abstract is available for this paper.

• Publication year

  2005

• Venue

  International Symposium on Distributed Computing

• Publication date

  2005-09-26

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/11561927_21
• 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

  2018influential reference
• Maximal independent sets in radio networks

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

  2005influential reference
• Distributed Algorithms for Coloring and Domination in Wireless Ad Hoc Networks

  2004cited by this paper
• Bypassing the embedding: algorithms for low dimensional metrics

  2004cited by this paper
• Bypassing the Embedding: Approximation schemes and Compact Representations for Low Dimensional Metrics

  2004cited by this paper
• Verifying Probabilistic Procedural Programs

  2004cited by this paper
• Unit disk graph approximation

  2004cited by this paper
• Triangulation and embedding using small sets of beacons

  2004cited by this paper
• Navigating nets: simple algorithms for proximity search

  2004cited by this paper
• Plongements lipschitziens dans Rn

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

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

  2002cited by this paper
• Robust position-based routing in wireless Ad Hoc networks with unstable transmission ranges

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

  1998cited by this paper
• Accessing Nearby Copies of Replicated Objects in a Distributed Environment

  1997cited by this paper
• Local-Global Phenomena in Graphs

  1993cited by this paper
• Improved distributed algorithms for coloring and network decomposition problems

  1992influential reference
• Locality in Distributed Graph Algorithms

  1992influential reference
• Network decomposition and locality in distributed computation

  1989cited by this paper
• Parallel symmetry-breaking in sparse graphs

  1987influential reference
• Distributed Computing: A Locality-Sensitive Approach

  1987cited by this paper
• A Fast and Simple Randomized Parallel Algorithm for Maximal Matching

  1986cited by this paper
• A simple parallel algorithm for the maximal independent set problem

  1985influential reference
• A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem

  1985cited by this paper
• Plongements lipschitziens dans ${\bbfR}\sp n$

  1983cited by this paper
• Journal of Graph Algorithms and Applications Low-distortion Embeddings of Trees

  year unknowninfluential reference

• Maximal Independent Set via Leader Election by Mobile Agents from Arbitrary Initial Configuration Without Global Knowledge

  2026cites this paper
• Singing a MIS

  2025cites this paper
• Fast Maximal Independent Sets on Dynamic Graphs

  2025cites this paper
• Approximate Distance Oracle for Fault-Tolerant Geometric Spanners

  2024cites this paper
• Graph Partition and Multiple Choice-UCB Based Algorithms for Edge Server Placement in MEC Environment

  2024influential citation
• Approximate Distance and Shortest-Path Oracles for Fault-Tolerant Geometric Spanners

  2023cites this paper
• Distributed Independent Sets in Interval and Segment Intersection Graphs

  2021cites 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
• An energy-efficient, self-stabilizing and distributed algorithm for maximal independent set construction in wireless sensor networks

  2019cites this paper
• Local Computation Algorithms

  2019cites this paper
• Optimal deterministic distributed algorithms for maximal independent set in geometric graphs

  2019cites this paper
• Low-congestion shortcut and graph parameters

  2019cites this paper
• Deterministic Distributed Ruling Sets of Line Graphs

  2018cites this paper
• Sublinear search spaces for shortest path planning in grid and road networks

  2018cites this paper
• Distributed Symmetry Breaking in Graphs with Bounded Diversity

  2018cites this paper
• Parallel Asynchronous Distributed-Memory Maximal Independent Set Algorithm with Work Ordering

  2017cites this paper
• Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching

  2017cites this paper
• Deterministic distributed construction of T-dominating sets in time T

  2017cites this paper
• Can We Locally Compute Sparse Connected Subgraphs?

  2017cites this paper
• LCL Problems on Grids

  2017cites this paper
• Distributed-memory fast maximal independent set

  2017cites this paper
• Randomised distributed MIS and colouring algorithms for rings with oriented edges in O(√(log n)) bit rounds

  2016cites this paper
• Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring

  2016cites this paper
• Spectral Inference of a Directed Acyclic Graph Using Pairwise Similarities

  2016cites this paper
• Design Patterns in Beeping Algorithms

  2016cites this paper
• Adversarial Input in Games and Markets

  2016cites this paper
• Design patterns in beeping algorithms: Examples, emulation, and analysis

  2016cites this paper
• The power of frequency hopping and information dissemination in constrained communication models

  2015cites this paper
• Tight Bounds for MIS in Multichannel Radio Networks

  2015cites this paper
• On Distributed Computing with Beeps

  2015cites this paper
• Directory Protocols for Distributed Transactional Memory

  2015cites this paper
• Computing in Additive Networks with Bounded-Information Codes

  2015cites this paper
• An effective redundancy detection method in wireless sensor network

  2014cites this paper
• Simple Neural-Like P Systems for Maximal Independent Set Selection

  2013cites this paper
• Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings

  2013cites this paper
• Almost Optimal Channel Access in Multi-Hop Networks with Unknown Channel Variables

  2013cites this paper
• Maximal independent sets in multichannel radio networks

  2013cites this paper
• Distributed Graph Coloring: Fundamentals and Recent Developments

  2013influential citation
• AND-NOT logic framework for steady state analysis of Boolean network models

  2012cites this paper
• Super-Fast 3-Ruling Sets

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

  2012cites this paper
• Towards better understanding of the behaviour of Bluetooth networks distributed algorithms

  2012cites this paper
• Analysis of energy efficient Self-organization scheduling Scheme for Ad Hoc WSN

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

  2012cites this paper
• Asynchronous leader election and MIS using abstract MAC layer

  2012influential citation
• Feedback from nature: an optimal distributed algorithm for maximal independent set selection

  2012cites this paper
• MIS on the fly

  2011cites this paper
• D C ] 1 0 Ju n 20 11 MIS on the fly ( Extended Abstract )

  2011cites this paper
• Space-efficient local computation algorithms

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

  2011cites this paper
• Thesis submitted in partial fulfillment of the requirements for the M.Sc. degree in the School of Computer Science, Tel-Aviv University

  2011cites this paper
• On the computation of fixed points in Boolean networks

  2011cites this paper
• Beeping a maximal independent set

  2011cites this paper
• Fast Local Computation Algorithms

  2011cites this paper
• Beeping an MIS

  2011cites this paper
• An optimal bit complexity randomized distributed MIS algorithm

  2011cites this paper
• COMBINE: An Improved Directory-Based Consistency Protocol

  2010cites this paper
• Algorithms and Models for Problems in Networking

  2010cites this paper
• Brief announcement: combine -- an improved directory-based consistency protocol

  2010cites this paper
• Distributed Algorithms for Approximating Wireless Network Capacity

  2010cites this paper
• What Is the Use of Collision Detection (in Wireless Networks)?

  2010cites this paper
• Empire of colonies: Self-stabilizing and self-organizing distributed algorithm

  2009cites this paper
• The abstract MAC layer

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

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

  2009cites this paper
• Routing on the geometry of wireless ad hoc networks

  2009cites this paper
• Positioning and Scheduling of Wireless Sensor Networks: Models, Complexity, and Scalable Algorithms

  2009cites this paper
• ( Δ + 1 )-COLORING IN LINEAR ( IN Δ ) TIME

  2009cites this paper
• An Optimal Bit Complexity Randomized Distributed MIS Algorithm (Extended Abstract)

  2009cites this paper
• Remote-spanners: What to know beyond neighbors

  2009cites this paper
• A stochastic vehicle mobility model with environmental condition adaptation capability

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

  2009cites this paper
• The coverage-control optimization in sensor network subject to sensing area

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

  2009cites this paper
• Distributed (δ+1)-coloring in linear (in δ) time

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

  2009cites this paper
• A Better Approximation for Minimum Average Routing Path Clustering Problem in 2-d Underwater Sensor Networks

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

  2009cites this paper
• Connected Dominating Sets

  2009cites this paper
• Fast Distributed Approximations in Planar Graphs

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

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

  2008influential citation
• What can be approximated locally?: case study: dominating sets in planar graphs

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

  2008cites this paper
• Distributed (Delta+1)-Coloring in Linear (in Delta) Time

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

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

  2008cites this paper
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition

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

  2008cites this paper
• 2 6 D ec 2 00 8 Distributed ( ∆ + 1 )-coloring in linear ( in ∆ ) time

  2008cites this paper
• Distributed packing in planar graphs

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

  2008cites this paper
• Local, distributed weighted matching on general and wireless topologies

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

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

  2008cites this paper
• Case Study: Dominating Sets in Planar Graphs

  2008cites this paper
• Domination Algorithms for Lifetime Problems in Self-organizing Ad hoc and Sensor Networks

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

  2007influential citation