×

Degree switching operations in networks and large scale systems assignment problems. (English) Zbl 0432.94026


MSC:

94C15 Applications of graph theory to circuits and networks
68Q25 Analysis of algorithms and problem complexity
93A15 Large-scale systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brayton, R. K.; Gustavson, F. G.; Willoughby, R. A., Some results on sparse matrices, Maths Comput., Vol. 24, 937-954 (1969) · Zbl 0233.65022
[2] (Rose, D. J.; Willoughby, R. A., Sparse Matrices and Their Applications. Sparse Matrices and Their Applications, Proc. IBM Conf. (1972), Plenum Press: Plenum Press New York)
[3] Tewarson, R. P., Sparse Matrices, Mathematics in Science and Engineering, Vol. 99 (1973), Academic Press: Academic Press New York · Zbl 0258.65035
[4] Ledet, W. P.; Himmelblau, D. M., Decomposition procedures for the solving of large scale systems, Adv. chem. Engng, Vol. 8, 186 (1970)
[5] Himmelblau, D. M., Morphology of decomposition, (Himmelblau, D. M., Decomposition of Large Scale Systems (1973), Elsevier: Elsevier New York) · Zbl 0267.65053
[6] Steward, D. V., Partitioning and tearing of systems of equations, SIAM J. Numer. Anal., Vol. 2, 345-365 (1965) · Zbl 0141.13502
[7] Cheung, L. K.; Kuh, E. S., The bordered triangular matrix and minimum essential sets of a digraph, IEEE Trans. Circuits and Systems, Vol. CAS-21, 633-639 (1974)
[8] Kevorkian, A. K., On bordered triangular or lower \(N\) forms of an irreducible matrix, IEEE Trans. Circuits and Systems, Vol. 23, 621-624 (1976) · Zbl 0355.65019
[9] Steward, D. V., Tearing analysis of the structure of disorderly sparse matrices, (Willoughby, R. A., Sparse Matrix Proceedings (1969), IBM Yorktown Heights: IBM Yorktown Heights New York), 65-74, Rep. No RAI 11707
[10] Kevorkian, A. K.; Snoek, J., Decomposition in large scale systems theory and applications in solving large sets of non-linear simultaneous equations, (Himmelblau, D. M., Decomposition of Large Scale Problems (1973)), 491-515, Amsterdam, North Holland
[12] Bhat, K. V.S.; Kinariwala, B., Optimum tearing in large scale systems and minimum feedback outsets of a digraph, J. Franklin Inst., Vol. 307, 83-94 (1979) · Zbl 0406.93018
[13] Bhat, K. V.S.; Kinariwala, B., Degree switching operations in graphs and its applications, (Proc. of the Eighth Hawaii Int. Conf. on System Sciences (1975), Western Periodicals), 261-263
[14] Rose, D. J.; Tarjan, R. E., Algorithmic aspects of vertex elimination on directed graphs, SIAM J. appl. Math., Vol. 34, 176-197 (1978) · Zbl 0377.65013
[15] Sangiovanni-Vincentelli, A., A graph theoretic interpretation of nonsymmetric permutation on sparse matrices, Int. J. Circuit Theory and Appl., Vol. 5, 139-147 (1977) · Zbl 0359.94049
[16] Bhat, K. V.S.; Kinariwala, B., An efficient algorithm for output set assignment in large scale systems, Large Scale Systems Theory and Applications, 147-153 (1976), Udine, Italy (Pittsburgh, PA, ISA 1976)
[17] Bhat, K. V.S.; Kinariwala, B., An algorithm for \(n\)×\(n\) optimum assignment problem, BIT (1979) · Zbl 0445.65022
[19] Kinariwala, B.; Bhat, K. V.S., Theory of output set assignments and the degree switching operations, SIAM J. Computing, Vol. 5, 589-601 (1976) · Zbl 0344.94022
[20] Kameda, T.; Munro, I., A
((O(∣V\)\t|;·\t|;\(E\)\t|;) algorithm for maximum matching of graphs, Computing, Vol. 12, 91-98 (1974) · Zbl 0278.65069
[21] Hopcroft, J. E.; Karp, R. M., An \(n^{52}\) algorithm for maximum matching in bipartite graphs, SIAM J. Comput, Vol. 2, 225-231 (1973) · Zbl 0266.05114
[22] Itai, A.; Rodeh, M.; Tanimoto, S. L., Some matching problems for bipartite graphs, J. Ass. Computg Mach., Vol. 24, No. 4, 517-525 (1978) · Zbl 0388.68059
[23] Valiant, L. G., The complexity of computing permanent, Theoretical Computer Science, Vol. 8, 189-201 (1979) · Zbl 0415.68008
[24] Vaniant, L. G., The Complexity of enumeration and reliability problems, SIAM J. Comput., Vol. 8, 110-124 (1979)
[25] Harary, F.; Norman, R. Z.; Cartwright, D., Structural Models: An Introduction to Theory of Directed Graphs (1965), John Wiley: John Wiley New York · Zbl 0139.41503
[26] Karp, R., Reducibility among combinatorial problems, (Miller, R.; Thatcher, J., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York), 85-104 · Zbl 0366.68041
[27] Tarjan, R., Depth-first search and linear graph algorithms, SIAM J. Computg, Vol. 1, 146-160 (1972) · Zbl 0251.05107
[29] Johnston, H. C.; Hoare, C. A.R., Matrix reduction—an efficient method, Communs. Ass. comput. Mach., Vol. 18, 141-150 (1975) · Zbl 0297.68031
[30] Tarjan, R. E., Complexity of combinatorial algorithms, SIAM Rev., Vol. 20, 457-491 (1978) · Zbl 0384.68045
[31] Murthy, K. G., An algorithm for ranking all the assignments in order of increasing costs, Ops Res., Vol. 16, 682-687 (1968) · Zbl 0214.18705
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.