4 papers
Theory on the Structure and Coloring of Maximal Planar Graphs (1)Recursion Formulae of Chromatic Polynomial and Four-Color Conjecture
Jin Xu
In this paper, two recursion formulae of chromatic polynomial of a maximal planar graph G are obtained. Moreover, the application of these formulaes to the proof of Four-Color Conj…
Probe Machine
Jin Xu
A novel computing model, called \emph{Probe Machine}, is proposed in this paper. Different from Turing Machine, Probe Machine is a fully-parallel computing model in the sense that…
Theory on Structure and Coloring of Maximal Planar Graphs (I): Relationship between Structure and Coloring
Jin Xu
Maximal planar graph refers to the planar graph with the most edges, which means no more edges can be added so that the resulting graph is still planar. The Four-Color Conjecture s…
Improved Exponential Time Lower Bound of Knapsack Problem under BT model
Xin Li, Tian Liu, Han Peng +2
M.Alekhnovich et al. recently have proposed a model of algorithms, called BT model, which covers Greedy, Backtrack and Simple Dynamic Programming methods and can be further divided…