Search

The graph centroids defined through a topological property of a graph called g-convexity found its application in various fields. They have classified under the "facility location" problem. However, the g-centroid location for an arbitrary graph is NP -hard. Thus, it is necessary to devise an approximation algorithm for general graphs and polynomial-time algorithms for some special classes of graphs. In this paper, we study the relationship between the g-centroids of composite graphs and their factors under various well-known graph operations such as graph Joins, Cartesian products, Prism, and the Corona. For the join of two graphs G 1 and G 2 , the weight sequence of the composite graph does not depend on the weight sequences of its factors; rather it depends on the incident pattern of the maximum cliques of G 1 and G 2 . We also characterize the structure of the g-centroid under various cases. For the Cartesian product of G 1 and G 2 and the prism of a graph, we establish the relationship between the g-centroid of a composite graph and its factors. Our results will facilitate the academic community to focus on the factor graphs while designing an approximate algorithm for a composite graph. [ABSTRACT FROM AUTHOR]

The broadcast performance of the 802.11 wireless protocol depends on several factors. One of the important factor is the number of nodes simultaneously contending for the shared channel. The Medium Access Control (MAC) technique of 802.11 is called the Distributed Coordination Function (DCF). DCF is a Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) scheme with binary slotted exponential backoff. A collision is the result of two or more stations transmitting simultaneously. Given the simplicity of the DCF scheme, it was adapted for Dedicated Short Range Communication (DSRC) based vehicular communication. A broadcast mechanism is used to disseminate emergency and safety related messages in a vehicular network. Emergency and safety related messages have a strict end-to-end latency of 100 ms and a Packet Delivery Ratio (PDR) of 90% and above. The PDR can be evaluated through the packet loss probability. The packet loss probability P L is given by, P L = 1 − ( 1 − P e )( 1 − P C ), where P e is the probability of channel error and P C is the probability of collision. P e depends on several environmental and operating factors and thus cannot be improved. The only way to reduce P L is by reducing P C . Currently, expensive radio hardware are used to measure P L . Several adaptive algorithms are available to reduce P C . In this paper, we establish a closed relation between P C and the Stirling number of the second kind. Simulation results are presented and compared with the analytical model for accuracy. Our simulation results show an accuracy of 99.9% compared with the analytical model. Even on a smaller sample size, our simulation results show an accuracy of 95% and above. Based on our analytical model, vehicles can precisely estimate these real-time requirements with the least expensive hardware available. Also, once the distribution of P C and P L are known, one can precisely determine the distribution of P e . [ABSTRACT FROM AUTHOR]

In this paper, we introduce the notion of g-convex weight sequence (gcws) for connected graphs based on the concept of g-convexity and g-weight. g-weight is a natural generalization of the notion of branch weight for trees. We investigate the various questions of realization of an integer sequence as a g-convex weight sequence for trees and some special classes of graphs such as complete graphs, windmill and degenerate windmill graphs and wheels. [ABSTRACT FROM AUTHOR]