* Independent Set (IS): In a graph G=(V,E), |V|=n, |E|=m, any set of nodes that are not adjacent
* Maximal Independent Set (MIS): An independent set that is no
subset of any other independent set
* Maximum Independent Set: A MIS of maximum size A graph G… …a MIS of G… …a MIS of max size
* Applications in Distributed Systems In a network graph consisting of nodes representing processors, a MIS defines a set of processors which can operate in parallel without interference
For instance, in wireless ad hoc networks, to avoid interference, a conflict graph is built, and a MIS on that defines a clustering of the nodes enabling efficient routing
* Applications in Distributed Systems (2) A MIS is always a Dominating Set (DS) of the graph (the converse in not true), namely every node in G must be at distance at most 1 from at least one node in the MIS
In a network graph G consisting of nodes representing processors, a MIS defines a set of processors which can monitor the correct functioning of all the nodes in G
* A Sequential Greedy algorithm Suppose that will hold the final MIS Initially
* Pick a node and add it to Phase 1:
* Remove and neighbors
* Remove and neighbors
* Pick a node and add it to Phase 2:
* Remove and neighbors
* Remove and neighbors
* Repeat until all nodes are removed Phases 3,4,5,…:
* Repeat until all nodes are removed No remaining nodes Phases 3,4,5,…,x:
* At the end, set will be an MIS of
* Worst case graph (for number of phases): n nodes, n-1 phases Running time of the algorithm: Θ(m) Number of phases of the algorithm: O(n)
* Homework Can you see a distributed version of the algorithm just given?
* A General Algorithm For Computing MIS Same as the sequential greedy algorithm,
but at each phase we may select
any independent set (instead of a single node)
* Suppose that will hold the final MIS Initially Example:
Comments