Disjoint Sets in Graphs and its Application to Electrical Networks
Abstract
Problem statement: One of the well known problems in Telecommunication and Electrical Power System is how to put Electrical Sensor Unit (ESU) in some various selected locations in the system. Approach: This problem was modeled as the vertex covering problems in graphs. The graph modeling of this problem as the minimum vertex covering set problem. Results: The degree covering set of a graph for every vertex is covered by the set minimum cardinality. The minimu of a graph cardinality of a degree covering set of a graph G is the degree covering number γP(G). Conclusion: We show that Degree Covering Set (DCS) problem is NP-complete. In this study, we also give a linear algorithm to solve the DCS for trees. In addition, we investigate theoretical properties of γP (T) in trees T.
DOI: https://doi.org/10.3844/jmssp.2011.73.77
Copyright: © 2011 Ford Lumban Gaol. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
- 4,223 Views
- 2,611 Downloads
- 0 Citations
Download
Keywords
- Electrical Sensor Unit (ESU)
- vertex covering
- Degree Covering Set (DCS)
- degree covering number
- electrical networks
- electrical power system
- graph modeling