Perfect matchings in random graphs with prescribed minimal degree

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Perfect matchings in random graphs with prescribed minimal degree

Full text

Pdf (757 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms table of contents

Baltimore, Maryland

SESSION: Session 3B table of contents

Pages: 148 - 157

Year of Publication: 2003

ISBN:0-89871-538-5

Authors

Alan Frieze	Carnegie Mellon University, Pittsburgh PA
Boris Pittel	Ohio State University, Columbus, OH

Sponsors

: SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 41, Citation Count: 0

Additional Information:

references index terms collaborative colleagues

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

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	Jonathan Aronson , Alan Frieze , Boris G. Pittel, Maximum matchings in sparse random graphs: Karp-Sipser revisited, Random Structures & Algorithms, v.12 n.2, p.111-177, March 1998 [doi>10.1002/(SICI)1098-2418(199803)12:2<111::AID-RSA1>3.0.CO;2-#]
	2	B. Bollobás, Random graphs, in Combinatorics (H.N.V. Temperley Ed.) London Mathematical Society Lecture Note Series 52, Cambridge University Press (1981) 80--102.
	3	B. Bollobás, T. Fenner and A.M. Frieze, Hamilton cycles in random graphs with minimal degree at least k, in A tribute to Paul Erdös, edited by A. Baker, B. Bollobás and A. Hajnal, (1988) 59--96.
	4	B. Bollobás, C. Cooper, T. Fenner and A.M. Frieze, On Hamilton cycles in sparse random graphs with minimum degree at least k, Journal of Graph Theory 34 (2000) 42--59.
	5	B. Bollobás and A.M. Frieze, On matchings and hamilton cycles in random graphs, Annals of Discrete Mathematics 28 (1985) 23--46.
	6	P. Erdös and A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960) 17--61.
	7	P. Erdös and A. Rényi, On random matrices, Publ. Math. Inst. Hungar. Acad. Sci. 8 (1964) 455--461.
	8	P. Erdös and A. Rényi, On the existence of a factor of degree one of a connected random graph, Acta. Math. Acad. Sci. Hungar. 17 (1966) 359--368.
	9	A M Frieze, Maximum matchings in a class of random graphs, Journal of Combinatorial Theory Series B, v.40 n.2, p.196-212, April 1986 [doi>10.1016/0095-8956(86)90077-8]
	10	M. Karonski and B. Pittel, Random proposals with a second chance for nerds, to appear.
	11	R.M. Karp and M. Sipser, Maximum matchings in sparse random graphs, Proceedings of the 22nd Annual IEEE Symposium on Foundations of Computing (1981) 364--375.
	12	L. Lovász, Combinatorial problems and exercises, Second edition, North-Holland, 1993.
	13	B.D.McKay, Asymptotics for symmetric 0--1 matrices with prescribed row sums, Ars Combinatoria 19A (1985) 15--25.
	14	R.W. Robinson and N.C. Wormald, Almost all regular graphs are Hamiltonian, Random Structures and Algorithms 5, (1994) 363--374.
	15	D.W. Walkup, Matchings in random regular bipartite graphs, Discrete Mathematics 31 (1980) 59--64.