I was wondering if a lot is known about independent sets in Random Geometric graphs? Most google searches don't bring up much. In addition I'm interested in any algorithms used for finding independent sets in Random Geometric Graphs.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ For RGGs generally, see Mark Walters: "Random geometric graphs", in Surveys in Combinatorics (LMS lecture series 392), CUP 2011. For independent sets, you can use google scholar as well as me - I found some discussion in an article "On the chromatic number of random geometric graphs", McDiarmid and Muller, 2011. Also, many papers on wireless sensor networks. $\endgroup$– user25199Sep 17, 2014 at 16:26
-
$\begingroup$ Do you know if i can get an online copy of the Survey Paper by Mark Walters? $\endgroup$– Pavan SanghaSep 17, 2014 at 19:39
-
$\begingroup$ The link provided at google scholar is nozdr.ru/data/media/biblioteka/kolxo3/M_Mathematics/MA_Algebra/… $\endgroup$– user25199Sep 18, 2014 at 8:34
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Unit disk graphs are a special type of random geometric graphs, where two of the given nodes on a plane share an edge if their Euclidean distance is less or equal to one. This class has been studied quite a lot and it is probably a good starting point for you. I'm not an expert, but here is a list of paper (and references therein) where I would start from (in chronological order).
- B. N. Clark, C. J. Colbourn, D. S. Johnson, Unit disk graphs (1990)
- J. Díaz, J. Petit, M. Serna, Random Geometric Problems on $[0, 1]^2$ (1999)
- T. Nieberg, J. Hurink, W. Kern, A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs (2005)
- W. Wua, H. Dub, X. Jiab, Y. Lic, S. C.H. Huangb, Minimum connected dominating sets and maximal independent sets in unit disk graphs (2006)
- C. Mcdiarmid, T. Müller, On the chromatic number of random geometric graphs (2011)
- D. Mahjoub, D. W. Matula, Experimental Study of Independent and Dominating Sets in Wireless Sensor Networks Using Graph Coloring Algorithms (2009)
- P. Hu, K. Xing, L. Huang, Y. Wang, D. Wang, P. Li, A Maximal Independent Set Based Giant Component Formation in Random Unit-Disk Graphs (2011)
$\begingroup$
$\endgroup$
4
see C. Mcdiarmid and T. M¨uller, “On the Chromatic Number of Random Geometric Graphs,” Combinatorica, vol. 31, no. 4, pp. 423-488, Nov. 2011
-
$\begingroup$ Thanks! Thats a pretty large document any ideas on where i can find more specific work to independent sets in the paper? $\endgroup$ May 26, 2015 at 11:16
-
$\begingroup$ As far as I remember, it was at the very beginning. see Theorem 3 of arxiv.org/abs/1311.5527 $\endgroup$– JeffMay 26, 2015 at 16:39
-
$\begingroup$ Ok thanks, but isn't theorem 3 concerning the chromatic number and not necessarily the independent set? $\endgroup$ May 27, 2015 at 9:02
-
$\begingroup$ First of all, there are many independent set, each can be obtained using a proper coloring. The independence number of a graph, that is, the cardinality of the maximum independent set, is unique and has several relationship with the chromatic number, see e.g., planetmath.org/sizeofmaximalindependentsetandchromaticnumber $\endgroup$– JeffMay 27, 2015 at 13:16