The Randomized Coloring Procedure with Symmetry-Breaking

DOI10.1007/978-3-540-70575-8_26MaRDI QIDQ3521929zbMATH OpenOpenAlexFDO

Authors Aravind Srinivasan, Sriram Pemmaraju

Publication date 28 August 2008

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-70575-8_26

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Recommendations

• Coloring random graphs
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Probabilistic arguments in graph coloring (invited talk)
• Graph colouring and the probabilistic method
• scientific article; zbMATH DE number 1833421

Cited in

(9)

• Non-independent randomized rounding and coloring
• scientific article; zbMATH DE number 1688362 (Why is no real title available?)
• scientific article; zbMATH DE number 7368393 (Why is no real title available?)
• Distributed algorithms for the Lovász local lemma and graph coloring
• A color-to-spin domino Schensted algorithm
• Exploiting symmetry for the job sequencing and tool switching problem
• Targeted least cardinality candidate key for relational databases
• Brooks-type theorem for r-frugal coloring of graphs
• Asymptotically optimal frugal colouring

This page was built for publication: The Randomized Coloring Procedure with Symmetry-Breaking

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3521929)