Further algorithmic aspects of the local lemma

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Further algorithmic aspects of the local lemma

Full text

Pdf (850 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 524 - 529

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

Michael Molloy	Department of Computer Science, University of Toronto, Toronto, Canada
Bruce Reed	Equipe Combinatoire, CNRS, Université Pierre et Marie Curie Paris, France

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 23, Citation Count: 17

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/276698.276866 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	M. Ajtai , J. Komlós , E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.1-9, December 1983 [doi>10.1145/800061.808726]
	2	M. Albert, A. Frieze and B. Reed, Multicoloured Hamilton Cycles, Electronic Journal of Combinatorics 2 (1995) ~RiO.
	3	N. Alon, A parallel algorithmic version of the Local Lemma, Random Structures and Algorithms, 2 (1991), 367- 378.
	4	N. Alon, C. McDiarmid and B. Reed, Acyclic colouring of graphs, Random Structures and Algorithms 2 (1991) 277- 288.
	5	J. Beck, An algorithmic approach to the Lovdsz Local Lemma, Random Structures and Algorithms, 2 (1991), 343 - 365.
	6	Andrei Z. Broder , Alan M. Frieze , Eli Upfal, Static and dynamic path selection on expander graphs (preliminary version): a random walk approach, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.531-539, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258646]
	7	P. Erd5s and J. Selfridge, On a combinatorial game, J. Comb. Th. (A) 14 (1973), 298- 301.
	8	Paul Erdős , Joel Spencer, Lopsided Lova´sz Local Lemma and Latin transversals, Discrete Applied Mathematics, v.30 n.2-3, p.151-154, Feb. 28, 1991
	9	P. ErdSs and L. Lov~sz, Problems and results on 3- chromatic hypergraphs and some related questions, in: "Tnfinite and Finite Sets" (A. Hajnal et. al. Eds), Colloq. Math. $oc. J. Bolyai 11, North Holland, Amsterdam, 1975, pp. 609-627.
	10	H. Hind, M. Molloy and B. Reed, Colouring a graph frugally, Combinatorica, to appear.
	11	Hugh Hind , Michael Molloy , Bruce Reed, Total Coloring With $\Delta + \mbox\lowercasepoly(\log \Delta)$ Colors, SIAM Journal on Computing, v.28 n.3, p.816-821, Feb. 1999 [doi>10.1137/S0097539795294578]
	12	A. Johansson, The choice number of spars~ graphs, manuscript.
	13	Jeff Kahn, Asymptotically good list-colorings, Journal of Combinatorial Theory Series A, v.73 n.1, p.1-59, Jan. 1996 [doi>10.1006/jcta.1996.0001]
	14	J.H. Kim, On Brooks' Theorem for sparse graphs, Combinatorics, Probability and Computing 4 (1995), 97- 132.
	15	F.T. Leighton, B. Maggs and $. Rao Packet routing and job-shop scheduling in O(congestion 4- dilation) steps~ Combinatorica 14 (1994), 167- 180.
	16	C. McDiarmid, H~ergraph colouring and the Lovdsz Local Lamina, manuscript.
	17	M. Molloy and B. Reed, A bound on tha total chromatic number, submitted.
	18	B. Reed, X,A, and ~o, Journal of Graph Theory, to appear.

CITED BY 17

	C. R. Subramanian, Analysis of a heuristic for acyclic edge colouring, Information Processing Letters, v.99 n.6, p.227-229, 30 September 2006
	Mohammad R. Salavatipour, A (1 + ε)-approximation algorithm for partitioning hypergraphs using a new algorithmic version of the Lovász Local Lemma, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Bruce Reed , Benny Sudakov, Asymptotically the list colouring constants are 1, Journal of Combinatorial Theory Series B, v.86 n.1, p.27-37, September 2002
	Anna Fiedorowicz , Mariusz Hałuszczak , Narayanan Narayanan, About acyclic edge colourings of planar graphs, Information Processing Letters, v.108 n.6, p.412-417, November, 2008
	Aravind Srinivasan, Improved algorithmic versions of the Lovász Local Lemma, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.611-620, January 20-22, 2008, San Francisco, California
	Berthold Vöcking, Almost optimal permutation routing on hypercubes, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.530-539, July 2001, Hersonissos, Greece
	Michael Molloy , Bruce Reed, Asymptotically optimal frugal colouring, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.106-114, January 04-06, 2009, New York, New York
	Noga Alon , Vera Asodi, Edge Colouring with Delays, Combinatorics, Probability and Computing, v.16 n.2, p.173-191, March 2007
	Michael Molloy , Bruce Reed, Colouring graphs when the number of colours is nearly the maximum degree, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.462-470, July 2001, Hersonissos, Greece
	Petr Kolman , Christian Scheideler, Improved bounds for the unsplittable flow problem, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.184-193, January 06-08, 2002, San Francisco, California
	Mohammad R. Salavatipour, A (1 + ε)-approximation algorithm for partitioning hypergraphs using a new algorithmic version of the Lovász local Lemma, Random Structures & Algorithms, v.25 n.1, p.68-90, August 2004
	Artur Czumaj , Christian Scheideler, Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lovász local lemma, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.30-39, January 09-11, 2000, San Francisco, California, United States
	Artur Czumaj , Christian Scheideler, A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.38-47, May 21-23, 2000, Portland, Oregon, United States
	Journal of Discrete Mathematics Staff, Research problems, Discrete Mathematics, v.257 n.2-3, p.599-624, 28 November
	Tom Leighton , Satish Rao , Aravind Srinivasan, New algorithmic aspects of the Local Lemma with applications to routing and partitioning, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.643-652, January 17-19, 1999, Baltimore, Maryland, United States
	Amitabha Bagchi , Amitabh Chaudhary , Petr Kolman, Short length Menger's theorem and reliable optical routing, Theoretical Computer Science, v.339 n.2, p.315-332, 12 June 2005
	T-H. Hubert Chan , Anupam Gupta , Kunal Talwar, Ultra-low-dimensional embeddings for doubling metrics, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.333-342, January 20-22, 2008, San Francisco, California