Selected Publications Joseph Culberson
-
Frozen Development in Graph Coloring
Joseph Culberson and Ian P. Gent
APES-19-2000 APES Research
Report
A mirror
Copy at UofA
- Empirical Evidence for an Asymptotic Discontinuity
in the Backbone of the 3-Coloring Phase Transition
Joseph Culberson and Ian P. Gent
APES-16-1999 APES Research
Report
A mirror
Copy at UofA
- On the Completeness of WalkSAT for 2-SAT
Joseph Culberson and Ian P. Gent
APES-15-1999 APES Research
Report
A mirror
Copy at UofA
- Well out of reach: Why hard problems are hard .
Joseph Culberson and Ian P. Gent
APES-13-1999 APES Research
Report
A mirror
Copy at UofA
-
On the Futility of Blind Search: An Algorithmic View of "No Free Lunch".
Joseph Culberson.
Evolutionary Computation Journal
6(2):109--128, 1998.
No Free Lunch versus NP; adversaries, algorithms
and knowledge trade-offs.
Technical
Report Version
-
The Gn,m Phase Transition is Not Hard for the
Hamiltonian Cycle Problem
Vandegriend, B. and Culberson, J.
Journal of Artificial Intelligence Research,
Volume 9,
pages 219-245,1998.
-
Searching with Pattern Databases with Jonathan Schaeffer.
Awarded "Best Paper" AI'96. Advantages of applying special knowledge to
a favorite AI search problem.
-
Hiding our colors with Adam Beacham and Denis Papp.
Adversaries and algorithms played on the graph coloring problem.
-
Mutation-Crossover Isomorphisms and the Construction of Discriminating
Functions. Landscape analysis, and how,
given an adversarial problem for crossover, to construct one
for mutation and vice versa.
-
On Searching A-ary Hypercubes and Related Graphs
with Jonathan Lichtner. Tricky adversaries
that discriminate on algorithmic detail and how to limit
the effectiveness of adversaries under some assumptions.
-
Sokoban is PSPACE-complete
Preprint in HTML format. Available as
postscript (417K) technical report TR97-02.
in Proceedings in Informatics 4, Fun With Algorithms, E. Lodi, L. Pagli and N.
Santoro Eds. pp 65-76, Carleton Scientific, Waterloo. 1999
Joe Culberson
Thu Jun 12 11:10:03 MDT 1997