| Abstract: | We present a heuristic for finding a small independent dominating set ?? of cubic graphs. We analyze the performance of this heuristic, which is a random greedy algorithm, on random cubic graphs using differential equations, and obtain an upper bound on the expected size of ??. A corresponding lower bound is derived by means of a direct expectation argument. We prove that ?? asymptotically almost surely satisfies 0.2641n ≤ |??| ≤ 0.27942n. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 147–161, 2002 |
