Some Matching Problems for Bipartite Graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Some Matching Problems for Bipartite Graphs

Full text

Pdf (567 KB)

Source

Journal of the ACM (JACM) archive
Volume 25 , Issue 4 (October 1978) table of contents

Pages: 517 - 525

Year of Publication: 1978

ISSN:0004-5411

Authors

Steven L. Tanimoto	Department of Computer Science, University of Washington, Seattle, WA and University of Connecticut, Storrs, Connecticut
Alon Itai	Computer Science Department, Techmon-Israel Institute of Technology, Haifa, Israel
Michael Rodeh	IBM Israel Scientific Center, Haifa, Israel

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 124, Citation Count: 7

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/322092.322093 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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
	3	DIJKSTRA, E W A note on two problems m connexion with graphs Numer Math 1 (1959), 269-271
	4	Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
	5	EVEN, S Algorahmtc Combmatortcs MacMillan, New York, 1973
	6	EVEN, S, ITAI, A, AND SnAreR, A On the complexity of timetable and multi-commodity flow SlAM J Comptng. 5 (1976), 691-703
	7	EWN, S, AND KARIV, O An O(n 2) algorithm for maximum matchmgs m general graphs Proc 16th Symp on Foundations of Comptng, 1975, pp. 382-399
	8	FORD JR, C R, AND FULKERSON, D R Flows m Networks Princeton U. Press, Pnnceton, N J, 1962
	9	FREUDER, E C Synthesizing constraint expressions A 1 Memo 370, Artlf lntell Lab, M I T, Cambridge. Mass, July 1976
	10	Harold N. Gabow, An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs, Journal of the ACM (JACM), v.23 n.2, p.221-234, April 1976 [doi>10.1145/321941.321942]
	11	GABOW, H N, AND LAWLER, E An effioent implementation of Edmonds' algorithm for maximum matching on graphs Rep CV-CS-075-75, Dept Comptr Sci, U of Colorado, Boulder, ColD, 1975
	12	GAL, S, AND BREITBART, Y A method for obtaining all the solutions of a perfect matching problem TR-16, IBM Israel Scientific Ctr, Haffa, Israel, 1974
	13	HOPCROFT, J E, AND KARP. R M An n 52 algorithm for maxmmm matching m bipartite graphs SlAM J Comping 2 (1973), 225-231
	14	Alon Itai , Michael Rodeh, Finding a minimum circuit in a graph, Proceedings of the ninth annual ACM symposium on Theory of computing, p.1-10, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803390]
	15	KAMEDA, T, AND MUNRO, 1 A O(I VI IEI) algorithm for maximum matchmgs of graphs Computing 12 (1974), 91-98
	16	LANG, L L, AND STARKEr, J D An O(e log n) shortest path algorithm for sparse graphs (abstract) In Traub. J F. (Ed), Proc Symp Algorithms and Complexity, Carnegie-Mellon U. Aprd 1976. p 476
	17	Alan K. Mackworth, Consistency in Networks of Relations, University of British Columbia, Vancouver, BC, Canada, 1975
	18	RYSER, J R Combinatorial Mathematics Math Assoc Amer, dtst John Wiley, New York, 1963
	19	TANIMOTO, S L Analysts of btomedtcal tmages usmg maxtmal matchmg Proc 1976 IEEE Conf Decision and Control Adaptive Processes, Clearwater Beach, Fla, Dec 1976, pp 171-176
	20	Robert A. Wagner, A Shortest Path Algorithm for Edge-Sparse Graphs, Journal of the ACM (JACM), v.23 n.1, p.50-57, Jan. 1976 [doi>10.1145/321921.321927]
	21	WALTZ, D Understandmg line drawmgs of scenes with shadows In The Psychology of Computer Vlston, P H Wmston, Ed, McGraw-Hill, New York, 1975, pp 19-91

CITED BY 7

	Christos H. Papadimitriou , Mihalis Yannakakis, The complexity of restricted spanning tree problems, Journal of the ACM (JACM), v.29 n.2, p.285-309, April 1982
	Vadim E. Levit , Eugen Mandrescu, Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings, Discrete Applied Mathematics, v.132 n.1-3, p.163-174, 15 October 2003
	Harold Gabow , Tadayoshi Kohno, A Network-Flow-Based Scheduler: Design, Performance History, and Experimental Analysis, Journal of Experimental Algorithmics (JEA), 6, p.3-es, 2001
	Whoi-Yul Kim , Avinash C. Kak, 3-D Object Recognition Using Bipartite Matching Embedded in Discrete Relaxation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.3, p.224-251, March 1991
	Jérôme Monnot, The labeled perfect matching in bipartite graphs, Information Processing Letters, v.96 n.3, p.81-88, 15 November 2005
	Irena Rusu, Maximum weight edge-constrained matchings, Discrete Applied Mathematics, v.156 n.5, p.662-672, March, 2008
	V. E. Levit , Eugen Mandrescu, Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids, Discrete Applied Mathematics, v.155 n.18, p.2414-2425, November, 2007