On Algorithms for Obtaining a Maximum Transversal

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On Algorithms for Obtaining a Maximum Transversal

Full text

Pdf (943 KB)

Source

ACM Transactions on Mathematical Software (TOMS) archive
Volume 7 , Issue 3 (September 1981) table of contents

Pages: 315 - 330

Year of Publication: 1981

ISSN:0098-3500

Author

I. S. Duff

Computer Science and Systems Division, Building 8.9, AERE Harewell, Oxon, England

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 55, Citation Count: 20

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/355958.355963 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BERGE, C. The Theory of Graphs Methuen, London, 1962.
	2	BUNCH, J.R., AND ROSE, D J., Eds In Proc Conf. Sparse Matrix Computations (Argonne National Laboratory, Sept 9-11, 1975), Academic Press, New York, 1976.
	3	DUFF, I.S. Analysis of sparse systems. Ph.D. thesis, Oxford, England, 1972.
	4	DUFF, I.S On permutations to block triangular form. J. Inst Math. Appl. 19 (1977), 339-342
	5	DUFF, I S. A survey of sparse matrix research. Proc IEEE 65 (1977), 500-535.
	6	I. S. Duff, Algorithm 575: Permutations for a Zero-Free Diagonal [F1], ACM Transactions on Mathematical Software (TOMS), v.7 n.3, p.387-390, Sept. 1981 [doi>10.1145/355958.355968]
	7	I. S. Duff , J. K. Reid, An Implementation of Tarjan's Algorithm for the Block Triangularization of a Matrix, ACM Transactions on Mathematical Software (TOMS), v.4 n.2, p.137-147, June 1978 [doi>10.1145/355780.355785]
	8	DULMAGE, A L, AND MENDELSOHN, N.S. A structure theory of b~partlte graphs of finite exterior dimension Trans Roy Soc. Can 53, Sec. 3 (1959), 1-13
	9	DULMAGE, A L., AND MENDELSOHN, N.S. Two algorithms for bipartite graphs. J. SIAM 11 (1963), 183-194.
	10	FORD, L.R, JR., AND FULKERSON, D.R. Flows in Networks. Princeton University Press, Princeton, N.J., 1962.
	11	GUSTAVSON, F.G. Finding the block lower triangular form of a matrix. In Sparse Matrix Computations, J.R. Bunch and D J. Rose (Eds.), Academic Press, New York, 1976.
	12	HALL, M. An algorithm for distinct representatives. Am. Math. Monthly 63 (1956), 716-717.
	13	HALL, P. On representatives of subsets. J. London Math. Soc. 10, 37, pt. 1 (1935), 26-30
	14	HARARY, F. Graph Theory. Addison-Wesley, Reading, Mass., 1969
	15	HOPCROFT, J.E., AND KARP, R.M. An n5/2 algorithm for maximum matchings in bipartite graphs SIAM J. Comput. 2 (1973), 225-231.
	16	SETTLER, P., AND WEIL, R. An algor,thm to provide structure for decomposition. In Proc Syrup on Sparse Matrices and their Apphcat~ons, R A. Willoughby (Ed.), IBM Rep. RA (11707), Yorktown Heights, N Y, 1969.
	17	KONI6, D. Theor~e der endhchen und unendhchen Graphen Chelsea, New York, 1950.
	18	KUHS, H W. The Hungarian method for solving the assignment problem. Naval Res. LogLst. Quart. 2 (1955), 83-97.
	19	KUHN, H W Variants of the Hungarian method for assignment problems Naval Res Logzst Quart 3 (1957), 253-258.
	20	STEWARD, D.V. On an approach to techniques for the analysis of the structure of large systems of equations. SIAM Rev. 4 (1962), 321-342
	21	STEWARD, D.V Partitioning and tearing systems of equations. SIAM J Numer. Anal. 2 (1965), 345-365.
	22	TARJAN, R. Depth-f'wst search and linear graph algorithms. SIAM J Comput 1 (1972), 146-160
	23	WIBER6, T. Permutation of an unsymmetric matrix to block triangular form. Ph.D. dissertation, Dep of Informatzon Processing, Univ. Ume~, Ume~, Sweden, March 1977
	24	WILLOUGHBY, R.A. Ed., Proc. Syrup. on Sparse Matrices and thew Applications, IBM Rep. RA 1 (11707), Yorktown Heights, N.Y., 1969.

CITED BY 20

	Thomas F. Coleman , Anders Edenbrandt , John R. Gilbert, Predicting fill for sparse orthogonal factorization, Journal of the ACM (JACM), v.33 n.3, p.517-532, July 1986
	I. S. Duff , J. K. Reid, The design of MA48: a code for the direct solution of sparse unsymmetric linear systems of equations, ACM Transactions on Mathematical Software (TOMS), v.22 n.2, p.187-226, June 1996
	Alex Pothen , Chin-Ju Fan, Computing the block triangular form of a sparse matrix, ACM Transactions on Mathematical Software (TOMS), v.16 n.4, p.303-324, Dec. 1990
	Kai Shen , Xiangmin Jiao , Tao Yang, Elimination forest guided 2D sparse LU factorization, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.5-15, June 28-July 02, 1998, Puerto Vallarta, Mexico
	K. A. Gallivan , B. A. Marsolf , H. A. G. Wijshoff, The parallel solution of nonsymmetric sparse linear systems using the H* reordering and an associated factorization, Proceedings of the 8th international conference on Supercomputing, p.419-430, July 11-15, 1994, Manchester, England
	Joseph W. H. Liu, A graph partitioning algorithm by node separators, ACM Transactions on Mathematical Software (TOMS), v.15 n.3, p.198-219, Sept. 1989
	I. S. Duff, Algorithm 575: Permutations for a Zero-Free Diagonal [F1], ACM Transactions on Mathematical Software (TOMS), v.7 n.3, p.387-390, Sept. 1981
	Iain S. Duff , Torbjörn Wiberg, Remarks on implementation of O(n^1/2τ) assignment algorithms, ACM Transactions on Mathematical Software (TOMS), v.14 n.3, p.267-287, Sept. 1988
	David Marple, A hierarchy preserving hierarchical compactor, Proceedings of the 27th ACM/IEEE conference on Design automation, p.375-381, June 24-27, 1990, Orlando, Florida, United States
	Ove Edlund, A software package for sparse orthogonal factorization and updating, ACM Transactions on Mathematical Software (TOMS), v.28 n.4, p.448-482, December 2002
	Timothy A. Davis , John R. Gilbert , Stefan I. Larimore , Esmond G. Ng, A column approximate minimum degree ordering algorithm, ACM Transactions on Mathematical Software (TOMS), v.30 n.3, p.353-376, September 2004
	Jeffery L. Kennington , Riad A. K. Mohamed, Recovery from Numerical Instability during Basis Reinversion, Computational Optimization and Applications, v.8 n.1, p.57-71, July 1997
	Cong Fu , Tao Yang, Sparse LU factorization with partial pivoting on distributed memory machines, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.31-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States
	Xiaoye S. Li , James W. Demmel, Making sparse Gaussian elimination scalable by static pivoting, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-17, November 07-13, 1998, San Jose, CA
	Cong Fu , Xiangmin Jiao , Tao Yang, Efficient Sparse LU Factorization with Partial Pivoting on Distributed Memory Architectures, IEEE Transactions on Parallel and Distributed Systems, v.9 n.2, p.109-125, February 1998
	Timothy A. Davis, A column pre-ordering strategy for the unsymmetric-pattern multifrontal method, ACM Transactions on Mathematical Software (TOMS), v.30 n.2, p.165-195, June 2004
	Iain S. Duff , Jennifer A. Scott, Stabilized bordered block diagonal forms for parallel sparse solvers, Parallel Computing, v.31 n.3+4, p.275-289, March/April 2005
	Jonas Larsson, A Framework for Implementation-Independent Simulation Models, Simulation, v.82 n.9, p.563-579, September 2006
	Frédéric Goualard , Christophe Jermann, A Reinforcement Learning Approach to Interval Constraint Propagation, Constraints, v.13 n.1-2, p.206-226, June 2008
	M. Sh. Levin, Combinatorial optimization in system configuration design, Automation and Remote Control, v.70 n.3, p.519-561, March 2009