**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**30169

##### An efficient Activity Network Reduction Algorithm based on the Label Correcting Tracing Algorithm

**Authors:**
Weng Ming Chu

**Abstract:**

**Keywords:**
Series/Parallel network,
Stochastic network,
Network
reduction,
Interdictive Graph,
Complexity Index.

**Digital Object Identifier (DOI):**
doi.org/10.5281/zenodo.1086173

**References:**

[1] Adlakha, V.G. & Kulkarni, V.G., "A classified bibliography of research on stochastic PERT networks: 1966-1987", Information Systems and Operational Research, 27, n3, 272-296, 1989.

[2] Bein,W.W., Kamburowski, J. and Stallmann, M.F.M., "Optimal reduction of two-terminal directed acyclic graphs," SIAM J. Computing, 21, 1112-1129, 1992.

[3] Burt J.M., Garman M.B., "Conditional Monte Carlo: A simulation technique for stochastic network analysis", Management Science, 18, 3, 1971.

[4] Colby, A.H., Elmaghraby S.E., "On the complete reduction of directed acyclic graphs", OR Report No. 197, N.C. State Univ., Raleigh, NC., 1984.

[5] Dodin, B.M., "Determining the K most critical paths in PERT networks", Operations Research, 32, n4, 859-877, 1984.

[6] Dodin, B.M., "Approximating the distribution function in stochastic networks",Computers and Operations Research, 12, n3, 251-264,1985.

[7] Duffin, R, "Topology ofseries-parallel networks", J. Math. Anal. Appl., 10, pp. 303-318, 1965.

[8] Fisher, D.L., Saisi, D. & Goldstein, W.M., "Stochastic PERT networks: op diagrams, critical paths and the project completion time", Computers and Operations Research,12-5, 471-482, 1985.

[9] Harley, H.O., Wortham, A.W., "A statistical theory for PERT critical path analysis", Management Science, 12, n 10, 469-481, 1966.

[10] Kamburowski, J., Michael, D.J., Stallman, M.F.M., "Minimizing the complexity index of an activity network", Networks, 36, 47-52, 2000.

[11] Kleindorfer G.B., "Bounding distributions for stochastic logic", Operations Research, 19, 7, 1586-1601, 1971.

[12] Kleindorfer, G.B., "Bounding distributions for a stochastic acyclic network", Journal of Operations Research, 19-7, 1586-1601, 1977.

[13] Martin, J.J., "Distribution of the time through a directed acyclic network", Operational Research, 13, 46-66, 1965.

[14] Ringer, L.J., "Numerical operators for statistical PERT critical path analysis", Management Science, 16, 136-143, 1969.

[15] Robillard, P., Trahan, M., "The completion time of PERT networks", Operations Research. 25, 15-29, 1977.

[16] Sahner R.A., Trivedi K.S., "Performance and reliability analysis using directed acyclic graphs", IEEE Transactions on Software Engineering, 13, 1105-1114, 1987.

[17] Splde, J.G., "Bounds for the distribution function of network variables", First Symposium of Operations Research, 3, 113-123, 1977.

[18] Van, Slyke, R.M., "Monte Carlo methods and the PERT problem", Operations Research, 11, 839-861, 1963.

[19] Yao, M.J., Chu, W.M., Tseng, T.Y., "A Label-Correcting Tracing Algorithm for the Approximation of the Probability Distribution Function of the Project Completion Time", Journal of Chinese Institute of Industrial Engineers, 24-2, p.153~165, March 2007.

[20] Yao, M.J., Chu, W.M., "A New Approximation Algorithm for Obtaining the Probability Distribution Function of the Project Completion Time", Computers and Mathematics with Applications., 54-2, p. 282~295, July 2007.