Random parallel algorithms for finding exact branchings, perfect matchings, and cycles. (English) Zbl 0827.68052

Summary: We devise randomized parallel algorithms which given a unary weighted (di)graph \(G = (V,E)\) construct in time \(O(\log^2 |V|)\) branchings, perfect matchings, and disjoint cycles of weight exactly \(k\) belonging to \(G\). Our algorithms improve previous solutions. Moreover, we give an \(\text{NC}^2\) algorithm for computing the absolute value of the pfaffian of a skew-symmetric matrix.


68W15 Distributed algorithms
Full Text: DOI


[1] Barahona, F., and W. R. Pulleyblank, Exact arborescences, matchings and cycles,Discrete Appl. Math.,16 (1987), 91-99. · Zbl 0632.05047 · doi:10.1016/0166-218X(87)90067-9
[2] Borodin, A., S. A. Cook, and N. Pippenger, Parallel computation for well-endowed rings and space bounded probabilistic machines,Inform, and Control,58 (1983), 113-136. · Zbl 0598.68043 · doi:10.1016/S0019-9958(83)80060-6
[3] Camerini, P. M., G. Galbriati, and F. Maffioli, Random pseudo-polynomial algorithms for exact matroid problem.J. Algorithms,13 (1992), 258-273. · Zbl 0773.05032 · doi:10.1016/0196-6774(92)90018-8
[4] Cook, S., A taxonomy of problems which have fast parallel algorithms,Inform, and Control,64 (1985), 2-22. · Zbl 0575.68045 · doi:10.1016/S0019-9958(85)80041-3
[5] Edmonds, J., Optimum branchings,J. Res. Nat. Bur. Standards,71B (1967), 233-240. · Zbl 0155.51204
[6] Galbiati, G., and F. Maffioli, Constructing an exact parity base is in RNC2, Report No. 91-022, Dip. di Elettronica, Polit, di Milano, 1991.
[7] Householder, A. S.,The Numerical Treatment of Single Nonlinear Equations, McGrawHill, New York, 1970. · Zbl 0242.65047
[8] Horowitz, E., and S. Sahni, On computing the exact determinant of matrices with polynomial entries,J. Assoc. Comput. Mack,22 (1975), 38-50. · Zbl 0293.65026
[9] Kirchhoff, G., ?ber die Ausfl?sung der Gleichungen auf welche man bei der Untersuchungen der Linearen Verteilung Galvanisher Str?me gef?rt wird,Poggendorf Ann. Phys.,72 (1947), 497-508.
[10] Karp, R. M., and V. Ramachandran, A survey of parallel algorithms for shared-memory machines, in: J. van Leeuwen, ed.,Handbook of Theoretical Computer Science, vol. A, North-Holland, Amsterdam, 1990, pp. 869-941. · Zbl 0900.68267
[11] Karp, R. M., E. Upfal, and A. Widgerson, The complexity of parallel search,J. Comput. System Sci.,36 (1988), 225-253. · Zbl 0651.68048 · doi:10.1016/0022-0000(88)90027-X
[12] Lov?sz, L., Computing ears and branchings in parallel,Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985, pp. 464-467.
[13] Mulmuley, K., U. V. Vazirani, and V. V. Vazirani, Matching is as easy as matrix inversion,Combinatorica,7 (1987), 105-113. · Zbl 0632.68041 · doi:10.1007/BF02579206
[14] Papadimitriou, C. H., and M. Yannakakis, The complexity of restricted spanning tree problems,J. Assoc. Comput. Mach.,29 (1982), 285-309. · Zbl 0478.68068
[15] Papadimitriou, C. H., and M. Yannakakis, The complexity of facets (and some facets of complexity),J. Comput. System Sci.,28 (1984), 244-259. · Zbl 0571.68028 · doi:10.1016/0022-0000(84)90068-0
[16] Schnorr, C., On self-transformable combinatorial problems,J. Assoc. Comput. Mach.,27 (1980), 701-717.
[17] Tutte, W. T., The factorization of linear graphs,J. London Math. Soc.,22 (1947), 107-111. · Zbl 0029.23301 · doi:10.1112/jlms/s1-22.2.107
[18] Tutte, W. T.,Graph Theory, Addison-Wesley, Reading, MA, 1984.
[19] Valiant, L. G., Relative complexity on checking and evaluating,Inform. Process. Lett.,5 (1976), 20-23. · Zbl 0342.68028 · doi:10.1016/0020-0190(76)90097-1
[20] Vazirani, V. V., NC algorithms for computing the number of perfect matchings in K3,3-free graphs and related problems,Inform. and Comput.,80 (1989), 152-163. · Zbl 0673.05075 · doi:10.1016/0890-5401(89)90017-5
[21] Wagner, K. W., More complicated questions about maxima and minima, and some closures of NP,Theoret. Comput. Sci.,51 (1987), 53-80. · Zbl 0653.03027 · doi:10.1016/0304-3975(87)90049-1
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.