Blelloch, Guy; Fineman, Jeremy; Shun, Julian (2012). "Greedy Sequential Maximal Independent Set and Matching are Parallel on Average". arXiv:1202.3205 [cs.DS].
Chiba & Nishizeki (1985). Chiba and Nishizeki express the condition of having O(n) edges equivalently, in terms of the arboricity of the graphs in the family being constant. Chiba, N.; Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing, 14 (1): 210–223, doi:10.1137/0214017, S2CID207051803.
Luby, M. (1986). "A Simple Parallel Algorithm for the Maximal Independent Set Problem". SIAM Journal on Computing. 15 (4): 1036–1053. CiteSeerX10.1.1.225.5475. doi:10.1137/0215074.
Métivier, Y.; Robson, J. M.; Saheb-Djahromi, N.; Zemmari, A. (2010). "An optimal bit complexity randomized distributed MIS algorithm". Distributed Computing. 23 (5–6): 331. doi:10.1007/s00446-010-0121-5. S2CID36720853.
Alon, Noga; Laszlo, Babai; Alon, Itai (1986). "A fast and simple randomized parallel algorithm for the maximal independent set problem". Journal of Algorithms. 7 (4): 567–583. doi:10.1016/0196-6774(86)90019-2.
Luby, M. (1986). "A Simple Parallel Algorithm for the Maximal Independent Set Problem". SIAM Journal on Computing. 15 (4): 1036–1053. CiteSeerX10.1.1.225.5475. doi:10.1137/0215074.
Chiba & Nishizeki (1985). Chiba and Nishizeki express the condition of having O(n) edges equivalently, in terms of the arboricity of the graphs in the family being constant. Chiba, N.; Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing, 14 (1): 210–223, doi:10.1137/0214017, S2CID207051803.
Métivier, Y.; Robson, J. M.; Saheb-Djahromi, N.; Zemmari, A. (2010). "An optimal bit complexity randomized distributed MIS algorithm". Distributed Computing. 23 (5–6): 331. doi:10.1007/s00446-010-0121-5. S2CID36720853.