11 citations · 20 across the 6 of their papers we have counts for
4 papers · 1 filter
Time series of Internet AS-level topology graphs: four patterns and one model
Lian-dong Liu, Ke Xu
Researchers have proposed a variety of Internet topology models. However almost all of them focus on generating one graph based on one single static source graph. On the other hand…
Exact phase transition of backtrack-free search with implications on the power of greedy algorithms
Liang Li, Tian Liu, Ke Xu
Backtracking is a basic strategy to solve constraint satisfaction problems (CSPs). A satisfiable CSP instance is backtrack-free if a solution can be found without encountering any…
On the Scaling Window of Model RB
Chunyan Zhao, Ke Xu, Zhiming Zheng
This paper analyzes the scaling window of a random CSP model (i.e. model RB) for which we can identify the threshold points exactly, denoted by or . For this model…
From k-SAT to k-CSP: Two Generalized Algorithms
Liang Li, Xin Li, Tian Liu +1
Constraint satisfaction problems (CSPs) models many important intractable NP-hard problems such as propositional satisfiability problem (SAT). Algorithms with non-trivial upper bou…