Representation of Edmonds' Algorithm for Finding Optimum Graph Branching on Associative Parallel Processors

1. Edmonds, J., Optimum Branchings, J. Res. Nat. Bur. Standards, 1967, no. 71B, pp. 233–240.

2. Gabow, H.N., Galil, Z., Spencer, T., and Tarjan, R.E., Efficient Algorithms for Finding Minimum Spanning Trees in Undirected and Directed Graphs, Combinatorica, 1986, vol. 6, no. 2, pp. 109–122.

   Google Scholar 

3. Gabow, H.N., Galil, Z., and Spencer, T., Efficient Implementation of Graph Algorithms Using Contraction, Proc. 25th Annual IEEE Symp. on Found. of Comp. Sci., 1984, pp. 347–357.

4. Tarjan, R.E., Finding Optimum Branchings, Networks, 1977, no.7, pp. 25–35.

   Google Scholar 

5. Camerini, R.M., Fratta, L., and Maffioli, F., A Note on Finding Optimum Branchigs, Networks, 1979, no. 9, pp. 309–312.

6. Fet, Y.I., Vertical Processing Systems: A Survey, IEEE, Micro, 1995, pp. 65–75.

7. Grosspietsch, K.E., Associative Processors and Memories: A Survey, IEEE, Micro, 1992, pp. 12–19.

8. Nepomniaschaya, A.Sh. and Vladyko, M.A., Comparison of Models of Associative Computations, Programmirovanie, 1997, no. 6, pp. 41–50.

9. Foster, C.C., Content Addressable Parallel Processors, New York: Van Nostrand Reinhold Co., 1976.

   Google Scholar 

10. Gabow, H.N. and Tarjan, R.E., Efficient Algorihms for a Family of Matroid Intersection Problems,J. Algorithms, 1984, no. 5, pp 80–131.

11. Karp, R.M., A Simple Derivation of Edmonds' Algorithm for Optimum Branchings, Networks, 1972, no.1, pp. 265–272.

    Google Scholar 

12. Nepomniaschaya, A.S., An Associative Version of the Prim-Dijkstra Algorithm and Its Application to Some Graph Problems,Andrei Ershov Second Int. Memorial Conf. “Perspectives of System Informatics,” Lecture Notes in Computer Science, Berlin: Springer, 1996, vol. 1181, pp. 203–213.

    Google Scholar 

13. Nepomniaschaya, A.S., Solution of Path Problems Using Associative Parallel Processors, Proc. of the Int. Conf. on Parallel and Distributed Systems, ICPADS'97, Seoul, Korea, IEEE Computer Society Press, 1997, pp. 610–617.

    Google Scholar 

14. Minieka, E., Optimization Algorithms for Networks and Graphs, New York: Marcel Decker, 1978. Translated under the title Algoritmy optimizatsii na setyakh i grafakh, Moscow: Mir, 1981.

    Google Scholar 

15. Nepomniaschaya, A.S., An Associative Algorithm for Finding Maximum-Weight Cycle in Directed Graphs, in Joint Bulletin of the Novosibirsk Computing Center and Ershov Institute of Informatics Systems, Computer Science Series, 1999, issue 11, pp. 45–58.

16. Tarjan, R.E., Depth First Search and Linear Graph Algorithms, SIAM J. Comput, 1972, vol. 1, pp. 146–160.

    Google Scholar 

17. Fredman, M.L. and Tarjan, R.E., Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms, J. ACM, 1987, vol. 34, no. 3, pp. 596–615.

    Google Scholar 

Download references