A. Broder, A. Frieze and E. Upfal, Static and Dynamic Path Selection on Ezpander Graphs: A Random Walk Approach, Proceedings of the 29th ACM Symposium on Theory of Computing (1997), 531 - 539.

Digital Library

Google Scholar

[7]

P. Erd5s and J. Selfridge, On a combinatorial game, J. Comb. Th. (A) 14 (1973), 298- 301.

Crossref

Google Scholar

[8]

P. ErdSs and J. Spencer, Lopsided Lovdsz Local Lemma and Latin transversals, Disc. App. Math. 30 (1990) 151 154.

Digital Library

Google Scholar

[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.

Google Scholar

[10]

H. Hind, M. Molloy and B. Reed, Colouring a graph frugally, Combinatorica, to appear.

Google Scholar

[11]

H. Hind, M. Molloy and B. Reed, Total colouring with A + poly(log A) colours. SIAM J. of Comp., to appear.

Digital Library

Google Scholar

[12]

A. Johansson, The choice number of spars~ graphs, manuscript.

Google Scholar

[13]

J. Kahn, Asymptotically good list-colorings, J. Combinatorial Th. (A), 73 (1996), 1 - 59.

Digital Library

Google Scholar

[14]

J.H. Kim, On Brooks' Theorem for sparse graphs, Combinatorics, Probability and Computing 4 (1995), 97- 132.

Crossref

Google Scholar

[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.

Google Scholar

[16]

C. McDiarmid, H~ergraph colouring and the Lovdsz Local Lamina, manuscript.

Google Scholar

[17]

M. Molloy and B. Reed, A bound on tha total chromatic number, submitted.

Google Scholar

[18]

B. Reed, X,A, and ~o, Journal of Graph Theory, to appear.

Google Scholar

Cited By

View all

Wang CYin Y(2024)A Sampling Lovász Local Lemma for Large Domain Sizes2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00019(129-150)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00019
Shu QLin G(2024)Planar graphs are acyclically edge $$(\Delta + 5)$$-colorableJournal of Combinatorial Optimization10.1007/s10878-024-01165-347:4Online publication date: 27-Apr-2024
https://doi.org/10.1007/s10878-024-01165-3
Wang WWang YYang W(2024)Acyclic Edge Coloring of 1-planar Graphs without 4-cyclesActa Mathematicae Applicatae Sinica, English Series10.1007/s10255-024-1101-z40:1(35-44)Online publication date: 3-Jan-2024
https://doi.org/10.1007/s10255-024-1101-z
Show More Cited By

Index Terms

Further algorithmic aspects of the local lemma
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
  2. Probability and statistics
    1. Probabilistic algorithms
    2. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods

Recommendations

Improved algorithmic versions of the Lovász Local Lemma
SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms

The Lovász Local Lemma is a powerful tool in combinatorics and computer science. The original version of the lemma was nonconstructive, and efficient algorithmic versions have been developed by Beck, Alon, Molloy & Reed, et al. In particular, the work ...
Commutativity in the Algorithmic Lovász Local Lemma

We consider the recent formulation of the algorithmic Lovász Local Lemma [N. Harvey and J. Vondrák, in Proceedings of FOCS, 2015, pp. 1327--1345; D. Achlioptas and F. Iliopoulos, in Proceedings of SODA, 2016, pp. 2024--2038; D. Achlioptas, F. Iliopoulos, ...
A Simple Algorithmic Proof of the Symmetric Lopsided Lovász Local Lemma
Learning and Intelligent Optimization
Abstract
We provide a simple algorithmic proof for the symmetric Lopsided Lovász Local Lemma, a variant of the classic Lovász Local Lemma, where, roughly, only the degree of the negatively correlated undesirable events counts. Our analysis refers to the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing

May 1998

684 pages

ISBN:0897919629

DOI:10.1145/276698

Chairman:
Jeffrey Vitter

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 May 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC98

Sponsor:

SIGACT

STOC98: The 30th Annual ACM Symposium on Theory of Computing

May 24 - 26, 1998

Texas, Dallas, USA

Acceptance Rates

STOC '98 Paper Acceptance Rate 75 of 169 submissions, 44%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

126
Total Citations
View Citations
681
Total Downloads

Downloads (Last 12 months)69
Downloads (Last 6 weeks)13

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Wang CYin Y(2024)A Sampling Lovász Local Lemma for Large Domain Sizes2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00019(129-150)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00019
Shu QLin G(2024)Planar graphs are acyclically edge $$(\Delta + 5)$$-colorableJournal of Combinatorial Optimization10.1007/s10878-024-01165-347:4Online publication date: 27-Apr-2024
https://doi.org/10.1007/s10878-024-01165-3
Wang WWang YYang W(2024)Acyclic Edge Coloring of 1-planar Graphs without 4-cyclesActa Mathematicae Applicatae Sinica, English Series10.1007/s10255-024-1101-z40:1(35-44)Online publication date: 3-Jan-2024
https://doi.org/10.1007/s10255-024-1101-z
Galanis AGuo HWang J(2023)Inapproximability of Counting Hypergraph ColouringsACM Transactions on Computation Theory10.1145/355855414:3-4(1-33)Online publication date: 1-Feb-2023
https://dl.acm.org/doi/10.1145/3558554
Bu YJia QZhu HZhu J(2022)Acyclic edge coloring of planar graphsAIMS Mathematics10.3934/math.20226057:6(10828-10841)Online publication date: 2022
https://doi.org/10.3934/math.2022605
Yang WWang YWang WLiu JFinbow SWang P(2022)Acyclic Chromatic Index of 1-Planar GraphsMathematics10.3390/math1015278710:15(2787)Online publication date: 5-Aug-2022
https://doi.org/10.3390/math10152787
Jain VPham HVuong T(2022)Towards the sampling Lovász Local Lemma2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00025(173-183)Online publication date: Feb-2022
https://doi.org/10.1109/FOCS52979.2021.00025
贾琪(2021)Acyclic Edge Coloring of Planar GraphsAdvances in Applied Mathematics10.12677/AAM.2021.10827610:08(2660-2672)Online publication date: 2021
https://doi.org/10.12677/AAM.2021.108276
Feng WHe KYin YKhuller SVassilevska Williams V(2021)Sampling constraint satisfaction solutions in the local lemma regimeProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451101(1565-1578)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451101
Shu QChen YHan SLin GMiyano EZhang A(2021)Acyclic edge coloring conjecture is true on planar graphs without intersecting trianglesTheoretical Computer Science10.1016/j.tcs.2021.06.017Online publication date: Jun-2021
https://doi.org/10.1016/j.tcs.2021.06.017
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Improved algorithmic versions of the Lovász Local Lemma

Commutativity in the Algorithmic Lovász Local Lemma

A Simple Algorithmic Proof of the Symmetric Lopsided Lovász Local Lemma