Open Access Open Access  Restricted Access Subscription or Fee Access

Graph Sampling by Spanning Tree under Stratified Setup

Sharad Pathak

Abstract


The sampling theory and its methodologies are based on assumption that the population under survey is of individuals and respondents have provided the answer of questions asked. When population is of graphical structure like containing nodes and edge links then it is complicated to apply the usual sampling procedures. Spanning tree is specified type of a graph, which is always connected with all nodes and becomes a sub-graph. Assume that there are several strata each having structure of graphical population of node-links, each contains graph like spanning tree. A sample containing different size from each stratum is drawn randomly. This paper presents a node-sampling procedure to draw sample and estimate the population mean- edge-length in the setup of stratified graphical structured population of spanning tree. An estimation procedure is suggested and expressions of mean squared error are obtained. Optimum choice of estimator parameter is obtained showing the control over bias as well as mean squared error both. A numerical case in point is given to support of theoretical findings. It is found that node-sampling procedure is worthwhile in stratified population structure.

 


Keywords


Spanning Tree, Node-Sampling Procedure, Bias, Mean Squared Error

Full Text:

PDF

References


⦁ Shukla D., Rajput Y.S., Thakur, N. S. Edge Estimation in population of planer graph using sampling. Journal of Reliability and Statistical Studies. 2010; 3: 13–29p.

⦁ Shukla D., Rajput Y.S., Thakur N. S. Edge Estimation in the Population of a Binary Tree Using Node-Sampling. Communication in Statistics-Theory and Methods. 2014; 43 (13): 2815–2829p.

⦁ Shukla D., Rajput Y.S., Thakur N. S. Estimation of spanning tree mean-edge using node sampling, Model Assisted Statistics and Applications. 2009; 4: 23–37p.

⦁ Deo, N. Graph Theory with Application to Engineering and Computer Science, Prentice-Hall, Eastern Economy Edition, New Delhi, India; 2001.

⦁ Krushal J.B. Jr. On the Shortest Spanning Sub Tree of Graph and the Traveling Salesman Problem. Proc. Am. Math. Soc. 1956; 7: 48–50p.

⦁ Naor J., Schieber B. Improved approximations for shallow-light spanning trees, 38th Annual Symposium on Foundations of Computer Science (FOCS '97). 1997; 536–545p.

⦁ Chen Y.S., Juang T.Y., Tseng E.H. Congestion-free embedding of multiple spanning trees in an arrangement graph. International conference on parallel and distributed systems (ICPADS '98). 1998; 360–367p.

⦁ Mao L.J., Lang S.D. Parallel algorithms for the degree-constrained minimum spanning tree problem using nearest- neighbor chains and the heap-traversal technique. International Conference on Parallel Processing Workshops (ICPPW '02). 2002; 398–406p.

⦁ Chem C., Morris S. Visualizing evolving networks: minimum spanning trees versus pathfinder networks. IEEE Symposium on Information Visualization. 2003; 9–15p.

⦁ Bader D.A., Cong G. A fast, parallel spanning tree algorithm for symmetric multiprocessors. 18th International Parallel and Distributed Processing Symposium (IPDPS '04). 38a, 2004; 75–81p.

⦁ Laszlo M., Mukherjee S. Minimum spanning tree partitioning algorithm for micro aggregation. IEEE transactions on knowledge and data engineering. 2005; 902–911p.

⦁ Yang L. Building k edge-disjoint spanning trees of minimum total length for isometric data embedding. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2005; 1680– 1683p.

⦁ Zou S., Nikolaidis I., Harms J.J. ENCAST: energy-critical node aware spanning tree for sensor networks. 3rd Annual Communication Networks and Services Research Conference (CNSR '05). 2005; 249–254p.

⦁ Goemans M.X. Minimum bonded degree spanning trees. 47th Annual IEEE symposium on foundations of computer science (FOCS '06). 2006; 273–282p.

⦁ Grygorash O., Zhou Y., Jorgensen Z. Minimum spanning tree based clustering algorithms. 18th IEEE International Conference on Tools with Artificial Intelligence (ICTAI' 06). 2006; 73–81p.

⦁ Yeung K.H., Yan F., Leung C. Improving network infrastructure security by partitioning networks running spanning tree protocol. International Conference on Internet Surveillance and Protection (ICISP '06). 2006; 19–29p.

⦁ Shukla D., Rajput Y.S., Thakur N.S. Estimation of spanning tree mean-edge using node sampling. Model Assisted Statistics and Applications. 2009; 4: 23–37p.

⦁ Shukla D., Rajput Y.S., Thakur N.S. Edge Estimation in population of planer graph using sampling. Journal of Reliability and Statistical Studies. 2010; 3: 13–29p.

⦁ Shukla D., Rajput Y.S., Thakur N.S. Edge Estimation in the Population of a Binary Tree Using Node-Sampling, Communication in Statistics- Theory and Methods, 2014; 43 (13): 2815–2829p.

⦁ Singh V.K., Shukla D. One parameter family of Factor-Type ratio estimator. Metron. 1987; 45 (1-2): 273–283p.

⦁ Singh V.K., Shukla D. An efficient one parameter family of Factor-Type estimators in sample Surveys. Metron. 1993; 51 (1-2): 139–159p.

⦁ Shukla D., Singh V.K., Singh G.N. On the use of transformation in factor type estimator, Metron. 1991; 49 (1-4): 349-361p.

⦁ Shukla D. F-T Estimator under two-phase sampling. Metron. 2002; 60: (1-2): 97–106p.

⦁ Sukhatme P.V., Sukhatme, B.V., Sukhatme S., Ashok C. Sampling Theory of Surveys with Applications, Iowa State University Press, I.S.A.S. Publication, New Delhi; 1984.

⦁ Singh D., Choudhary F.S. Theory and Analysis of Sample Survey Design. Wiley Eastern Limited, New Delhi. 1986.

⦁ Cochran W.G., Sampling Techniques. John Wiley and Sons, 5th Edition, New York; 2005


Refbacks

  • There are currently no refbacks.