Call for Paper - August 2022 Edition
IJCA solicits original research papers for the August 2022 Edition. Last date of manuscript submission is July 20, 2022. Read More

Connected Network Dominating Set of an Interval Graph

International Journal of Computer Applications
© 2012 by IJCA Journal
Volume 45 - Number 9
Year of Publication: 2012
A. Sudhakaraiah
V. Rama Latha

A Sudhakaraiah and Rama V Latha. Article: Connected Network Dominating Set of an Interval Graph. International Journal of Computer Applications 45(9):31-34, May 2012. Full text available. BibTeX

	author = {A. Sudhakaraiah and V. Rama Latha},
	title = {Article: Connected Network Dominating Set of an Interval Graph},
	journal = {International Journal of Computer Applications},
	year = {2012},
	volume = {45},
	number = {9},
	pages = {31-34},
	month = {May},
	note = {Full text available}


Connected dominating sets are useful in the computation of routing for mobile ad-hoc networks. A connected dominating set is used as a backbone for communications, and nodes that are not in this set communicate by passing messages through neighbors that are in the set. Recent advances in technology have made possible the creation of Wireless Sensor Networks. Although there is no physical backbone infrastructure, a virtual backbone can be formed by constructing a Connected Dominating Set (CDS). In this paper we present an algorithm for finding minimal connected network dominating set(MCNDS) of an interval graph


  • Teresa W. ; Hedetniemi, Stephen; Slater, Peter (1998a), Fundamentals of Domination in Graphs, Marcel Dekke.
  • Haynes, Teresa W. ; Hedetniemi, Stephen; Slater, Peter (1998b), Domination in Graphs: Advanced Topics, Marcel Dekker.
  • Hedetniemi, S. T. ; Laskar, R. C. , "Bibliography on domination in graphs and some basic definitions of domination parameters", Discrete Mathematics 86 (1–3): 257–277, 1990.
  • Sampathkumar, E. ; Walikar, HB, "The connected domination number of a graph", J. Math. Phys. Sci 13 (6): 607-613, 1979.
  • K. M. Alzoubi, P. J. Wan, and O. Frieder. Message-optimal connected-dominating- set construction for routing in mobile ad hoc networks. In MOBIHOC' 02,pages 157-164, 2002.
  • C. Adjih,P. Jacquet,and L. Viennot " Computing connected Dominated sets with multipoint relays," Technical Report 4597, INRIA-Rapport de recherché, Oct. 2002.
  • Maheswari. B, Lakshmi Naidu. Y, Naga muni Reddy. L, and A. Sudhakaraiah, "A polynomial time algorithm for finding a minimum independent neighbourhood set of an interval graph", Graph theory Notes of Newyork XLVI, 9-12,2004.
  • G. Ramalingan and C. Pandu Rangan ; "Unified approach to domination problems on interval graphs". Inform. Process Lett. , 27, 271-274,1989.
  • Guha, S. ; Khuller, S, "Approximation algorithms for connected dominating sets", Algorithmica 20 (4): 374–387, 1998.