Fomin; Gaspers & Saurabh (4-Graph Coloring Graph Coloring): Revision history

Jump to navigation Jump to search

Diff selection: Mark the radio buttons of the revisions to compare and hit enter or the button at the bottom.
Legend: (cur) = difference with latest revision, (prev) = difference with preceding revision, m = minor edit.

    15 February 2023

    • curprev 11:3511:35, 15 February 2023‎ Admin talk contribs‎ 654 bytes +654‎ 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..."
Retrieved from "https://algorithm-wiki.csail.mit.edu/wiki/Fomin;_Gaspers_%26_Saurabh_(4-Graph_Coloring_Graph_Coloring)"