An Average Case NP-complete Graph Colouring Problem

DOI10.1017/S0963548318000123MaRDI QIDQ4962593zbMATH OpenOpenAlexFDO

Authors Leonid A. Levin, Ramarathnam Venkatesan

Publication date 5 November 2018

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0963548318000123

zbMATH Keywords

random graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The complexity of some graph colouring problems
• The \(a\)-graph coloring problem
• scientific article; zbMATH DE number 3913673
• Minimum Coloring k-Colorable Graphs in Polynomial Average Time
• NP-completeness of edge-colouring some restricted graphs
• The complexity of generalized graph colorings
• Average-case complexity of backtrack search for coloring sparse random graphs
• The complexity of colouring problems on dense graphs
• On the total and AVD-total coloring of graphs

Cites work

• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• Average Case Complete Problems
• Average case completeness
• Expander graphs based on GRH with an application to elliptic curve cryptography
• Expected Computation Time for Hamiltonian Path problem
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• scientific article; zbMATH DE number 3960854 (Why is no real title available?)
• scientific article; zbMATH DE number 3574966 (Why is no real title available?)
• scientific article; zbMATH DE number 1256724 (Why is no real title available?)
• scientific article; zbMATH DE number 2123255 (Why is no real title available?)
• scientific article; zbMATH DE number 3310089 (Why is no real title available?)
• Lattice problems in NP ∩ coNP
• Matrix Transformation Is Complete for the Average Case
• Non-abelian analogs of lattice rounding
• Random Graph Isomorphism
• Random graphs.
• The development of the number field sieve
• The NP-completeness column: An ongoing guide
• The tale of one-way functions

Cited in

(6)

• Average polynomial time complexity of some NP-complete problems
• Short Note: A Las Vegas graph Colouring Algorithm
• Average-case complexity of backtrack search for coloring sparse random graphs
• On percolation and NP-hardness
• On percolation and \(\mathcal{NP}\)-hardness
• A hard problem that is almost always easy

This page was built for publication: An Average Case NP-complete Graph Colouring Problem

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