Average-case complexity of backtrack search for coloring sparse random graphs
From MaRDI portal
Publication:394742
DOI10.1016/j.jcss.2013.06.003zbMath1410.68173OpenAlexW2051236701MaRDI QIDQ394742
Anikó Szajkó, Zoltán Ádám Mann
Publication date: 27 January 2014
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2013.06.003
Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Backtrack: An O(1) expected time algorithm for the graph coloring problem
- Why almost all \(k\)-colorable graphs are easy to color
- A note on coloring sparse random graphs
- Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
- A note on the sharp concentration of the chromatic number of random graphs
- Zero knowledge and the chromatic number
- The concentration of the chromatic number of random graphs
- The hardest constraint problems: A double phase transition
- Heavy-tailed phenomena in satisfiability and constraint satisfaction problems
- Refining the phase transition in combinatorial search
- On-Line Coloring of Sparse Random Graphs and Random Trees
- Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces
- A theoretical analysis of backtracking in the graph coloring problem
- Almost all k-colorable graphs are easy to color
- On colouring random graphs
- The Complexity of Near-Optimal Graph Coloring
- New methods to color the vertices of a graph
- Exact and approximative algorithms for coloring G(n,p)
- Reducibility among Combinatorial Problems
- Evaluating the Kernighan-Lin Heuristic for Hardware/Software Partitioning
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Chromatic Scheduling and the Chromatic Number Problem
- The dynamics of proving uncolourability of large random graphs: I. Symmetric colouring heuristic
- Principles and Practice of Constraint Programming – CP 2004
- The two possible values of the chromatic number of a random graph
- The chromatic number of random graphs
- The chromatic number of random graphs
- Almost all graphs with average degree 4 are 3-colorable
- Frozen development in graph coloring