Syntax:
luby_find seed -i in1 -o out1.file out1.mr
Examples:
luby_find 982938 -i mre -o mis.list mis
Description:
This is a named command which computes a minimal independent set (MIS) of vertices for an undirected graph. A MIS contains vertices which do not share an edge and to which no additional vertex can be added. For a given graph there are typically many possible MIS's; the MIS that is computed is a function of the specified random number seed. The MIS is found by Luby's algorithm, which is an interative method. The MapReduce version of Luby's algorithm implemented by this command is discussed in the paper of (Plimpton).
See the named command doc page for various ways in which the -i inputs and -o outputs for a named command can be specified.
In1 stores a set of edges, assumed to have no duplicates or self-edges. This means that either (Vi,Vj) or (Vj,Vi) appears, but not both. Also (Vi,Vi) does not appear. The input is unchanged by this command.
Out1 will store the list of vertices in the MIS.
Related commands: none
(Luby) Luby, "A Simple Parallel Algorithm for the Maximal Independent Set Problem", SIAM J Computing, 15, 1036-1055 (1986).
(Plimpton) Plimpton and Devine, "MapReduce in MPI for Large-Scale Graph Algorithms", to appear in Parallel Computing (2011).