Fomin; Gaspers & Saurabh (4-Graph Coloring Graph Coloring)
Revision as of 10:35, 15 February 2023 by Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.7272}^n)$ == Space Complexity == $O(n)$ words (Derived: we store the sets I and C (in algorithm enumIS), and the maximum size of these sets is equal to the number of vertices in the graph. The algorithm also stores the solution sets S1 and S2, which have a maximum size equal to the number of vertices in the graph. We also call a 3-coloring algorithm, which likely has O(n) space complexity) == Description == == Approximate? == Exac...")
Time Complexity
$O({1.7272}^n)$
Space Complexity
$O(n)$ words
(Derived: we store the sets I and C (in algorithm enumIS), and the maximum size of these sets is equal to the number of vertices in the graph. The algorithm also stores the solution sets S1 and S2, which have a maximum size equal to the number of vertices in the graph. We also call a 3-coloring algorithm, which likely has O(n) space complexity)
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
2007
Reference
https://link.springer.com/chapter/10.1007/978-3-540-73545-8_9