Research Article
Connected Network Dominating Set of an Interval Graph
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 45 - Issue 9 |
| Published: May 2012 |
| Authors: A. Sudhakaraiah, V. Rama Latha |
10.5120/6809-9154
|
A. Sudhakaraiah, V. Rama Latha . Connected Network Dominating Set of an Interval Graph. International Journal of Computer Applications. 45, 9 (May 2012), 31-34. DOI=10.5120/6809-9154
@article{ 10.5120/6809-9154,
author = { A. Sudhakaraiah,V. Rama Latha },
title = { Connected Network Dominating Set of an Interval Graph },
journal = { International Journal of Computer Applications },
year = { 2012 },
volume = { 45 },
number = { 9 },
pages = { 31-34 },
doi = { 10.5120/6809-9154 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2012
%A A. Sudhakaraiah
%A V. Rama Latha
%T Connected Network Dominating Set of an Interval Graph%T
%J International Journal of Computer Applications
%V 45
%N 9
%P 31-34
%R 10.5120/6809-9154
%I Foundation of Computer Science (FCS), NY, USA
Abstract
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
References
- 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.
Index Terms
Keywords