tailieunhanh - Báo cáo toán học: "Minimum connected dominating sets of random cubic graphs"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Minimum connected dominating sets of random cubic graphs. | Minimum connected dominating sets of random cubic graphs W. Duckworth Department of Computing Macquarie University Sydney NSW 2109 Australia billy@ Submitted August 14 2001 Accepted February 14 2002. MR Subject Classifications 05C80 05C69 Abstract We present a simple heuristic for finding a small connected dominating set of cubic graphs. The average-case performance of this heuristic which is a randomised greedy algorithm is analysed on random n-vertex cubic graphs using differential equations. In this way we prove that the expected size of the connected dominating set returned by the algorithm is asymptotically almost surely less than . 1 Introduction A dominating set of a graph G is a subset D of the vertices of G such that for every vertex v of G either v 2D or there exists a vertex u 2D incident with v in G. A connected dominating set C of a graph G is a dominating set such that the subgraph induced by the vertices of C in G is connected. We are interested in finding connected dominating sets of small cardinality. For other basic graph theory definitions not defined here the reader is referred to 2 . The problem of finding a minimum connected dominating set of a graph is polynomially equivalent to finding a maximum leaf spanning tree of the graph. This well-known NP-hard optimisation problem 6 Problem ND2 is defined as follows. A spanning tree of a graph G is a connected spanning subgraph T of G that does not contain a cycle. Vertices of degree 1 in T are called leaves and we are interested in finding a spanning tree with a set of leaves of large cardinality. Note that the non-leaf vertices of T form a connected dominating set of G. This research was carried out whilst the author was in The Department of Mathematics Statistics The University of Melbourne VIC 3010 Australia THE ELECTRONIC JOURNAL OF COMBINATORICS 9 2002 R7 1 Solis-Oba 11 showed that the maximum leaf spanning tree problem is approximable with approximation ratio 2 improving .