@InProceedings{	  cs96,
  author	= "Joseph C. Culberson and Jonathan Schaeffer",
  title		= "Searching with Pattern Databases",
  pages		= "402--416",
  isbn		= "3-540-61291-2",
  editor	= "Gordon McCalla",
  booktitle	= "Proceedings of the Eleventh Biennial Conference of the
		  Canadian Society for Computational Studies of Intelligence
		  on Advances in Artificial Intelligence",
  month		= may # "~21--24",
  series	= "LNAI",
  volume	= 1081,
  publisher	= "Springer, Berlin",
  year		= 1996
}

@Article{	  cs98,
  author	= "Joseph C. Culberson and Jonathan Schaeffer",
  title		= "Pattern Databases",
  journal	= "Computational Intelligence",
  pages		= "318--334",
  volume	= 14,
  number	= 3,
  year		= 1998
}

@InProceedings{	  cul98,
  author	= "Joseph C. Culberson",
  title		= "Sokoban is {PSPACE}-complete",
  pages		= "65--76",
  isbn		= "1-894145-03-8",
  editor	= "Elena Lodi and Linda Pagli and Nicola Santoro",
  booktitle	= "Proceedings of the International Conference on Fun with
		  Algorithms ({FUN}-98)",
  month		= jun # "~18--20",
  publisher	= "Carleton Scientific, Waterloo, Ontario",
  year		= 1998
}

@InProceedings{	  ddo00,
  author	= "Erik D. Demaine and Martin L. Demaine and Joseph O'Rourke",
  title		= "{PushPush} and {Push-1} are {NP}-hard in {2D}",
  pages		= "211--219",
  booktitle	= "Proceedings of the 12th Canadian Conference on
		  Computational Geometry",
  address	= "Fredericton, New Brunswick, Canada",
  month		= aug # "16--18",
  year		= 2000
}

@InProceedings{	  do92,
  author	= "A. Dhagat and Joseph O'Rourke",
  title		= "Motion planning amidst movable square blocks",
  booktitle	= "Proceedings of the 4th Canadian Conference on
		  Computational Geometry",
  year		= 1992,
  pages		= "188--191",
  keywords	= "motion planning"
}

@Article{	  dz95,
  author	= "Dorit Dor and Uri Zwick",
  title		= "{SOKOBAN} and Other Motion Planning Problems",
  journal	= "CGTA: Computational Geometry: Theory and Applications",
  volume	= 13,
  number	= 4,
  pages		= "215--228",
  month		= "oct",
  year		= 1999
}

@InProceedings{	  ecai94*600,
  author	= "Jürgen Eckerle and Thomas Ottmann",
  title		= "An Efficient Data Structure for Bidirectional Heuristic
		  Search",
  pages		= "600--604",
  isbn		= "0-471-950696",
  editor	= "A. G. Cohn",
  booktitle	= "Proceedings of the Eleventh European Conference on
		  Artificial Intelligence",
  month		= aug # "~8--12",
  publisher	= "John Wiley and Sons, Chichester",
  year		= 1994
}

@InProceedings{	  ecai96*370,
  author	= "Jürgen Eckerle",
  title		= "{BDBIDA}: A New Approach for Space-limited Bidirectional
		  Heuristic Graph Search",
  pages		= "370--374",
  booktitle	= "{ECAI} '96; 12th European Conference on Artificial
		  Intelligence",
  isbn		= "0-471-96809-9",
  month		= aug,
  publisher	= "Wiley, Chichester -- New York -- Brisbane",
  year		= 1996
}

@InProceedings{	  ede97,
  author	= "Stefan Edelkamp",
  title		= "Suffix Tree Automata in State Space Search",
  pages		= "381--384",
  isbn		= "3-540-63493-2",
  editor	= "Gerhard Brewka and Christopher Habel and Bernhard Nebel",
  booktitle	= "Proceedings of the 21st Annual German Conference on
		  Artificial Intelligence ({KI}-97): Advances in Artificial
		  Intelligence",
  month		= sep # "~9--12",
  series	= "LNAI",
  volume	= 1303,
  publisher	= "Springer, Berlin",
  year		= 1997
}

@PhDThesis{	  ede99,
  author	= "Stefan Edelkamp",
  title		= "Datenstrukturen und {Lernverfahren} in der
		  {Zustandsraumsuche}",
  school	= "University of Freiburg, Germany",
  publisher	= "Infix Verlag",
  volume	= 201,
  year		= 1999
}

@InProceedings{	  ek98,
  author	= "Stefan Edelkamp and Richard E. Korf",
  title		= "The Branching Factor of Regular Search Spaces",
  pages		= "299--304",
  isbn		= "0-262-51098-7",
  booktitle	= "Proceedings of the 15th National Conference on Artificial
		  Intelligence and the 10th Conference on Innovative
		  Applications of Artificial Intelligence (AAAI-98/IAAI-98)",
  month		= jul # "~26--30",
  publisher	= "AAAI Press, Menlo Park, CA, USA",
  year		= 1998
}

@InProceedings{	  ell01,
  author	= "Stefan Edelkamp and A. L. Lafuente and S. Leue",
  title		= "Protocol Verification with Heuristic Search",
  booktitle	= "AAAI-Spring Symposium on Model-based Validation of
		  Intelligence",
  year		= 2001,
  pages		= "75--83"
}

@InProceedings{	  em01,
  author	= "Stefan Edelkamp and Ulrich Meyer",
  title		= "Theory and Practice of Time-Space Trade-Offs in Memory
		  Limited Search",
  booktitle	= "German Conference on Artificial Intelligence (KI-2001)",
  series	= "Lecture Notes in Computer Science",
  publisher	= "Springer",
  pages		= "169--184",
  year		= "2001"
}

@InProceedings{	  er98,
  author	= "Stefan Edelkamp and Frank Reffel",
  title		= "{OBDDs} in Heuristic Search",
  pages		= "81--92",
  isbn		= "3-540-65080-6",
  editor	= "Otthein Herzog and Andreas Günter",
  booktitle	= "Proceedings of the 22nd Annual German Conference on
		  Advances in Artificial Intelligence ({KI}-98)",
  month		= sep # "~15--17",
  series	= "LNAI",
  volume	= 1504,
  publisher	= "Springer, Berlin",
  year		= 1998
}

@InProceedings{	  es00,
  author	= "Stefan Edelkamp and Stefan Schrödl",
  title		= "Localizing {A*}",
  pages		= "885--890",
  booktitle	= "Proceedings of the 17th National Conference on Artificial
		  Intelligence and the 12th Conference on Innovative
		  Applications of Artificial Intelligence (AAAI-00/IAAI-00)",
  month		= jul # " ~30--~3",
  publisher	= "AAAI Press, Menlo Park, CA, USA",
  year		= 2000
}

@Article{	  es95,
  author	= "Jürgen Eckerle and Sven Schuierer",
  title		= "Efficient Memory-Limited Graph Search",
  journal	= "Lecture Notes in Computer Science",
  volume	= 981,
  pages		= "101--112",
  year		= 1995,
  coden		= "LNCSD9",
  issn		= "0302-9743",
  bibdate	= "Sat May 11 13:45:32 MDT 1996",
  acknowledgement=ack-nhfb
}

@Article{	  fb99,
  author	= "Gary W. Flake and Eric B. Baum",
  title		= "{Rush Hour} is {PSPACE}-complete, or ``{W}hy you should
		  generously tip parking lot attendants''",
  journal	= "Theoretical Computer Science",
  volume	= 270,
  pages		= "895-911",
  month		= jan,
  year		= 2002
}

@Article{	  ghosh:1991:bhs,
  author	= "Subrata Ghosh and Ambuj Mahanti",
  title		= "Bidirectional heuristic search with limited resources",
  journal	= "Information Processing Letters",
  volume	= 40,
  number	= 6,
  pages		= "335--340",
  day		= 30,
  month		= dec,
  year		= 1991,
  coden		= "IFPLAT",
  issn		= "0020-0190",
  bibdate	= "Wed Nov 11 12:16:26 MST 1998",
  acknowledgement=ack-nhfb,
  affiliation	= "Univ of Maryland",
  affiliationaddress="College Park, MD, USA",
  classification= "723; C1230 (Artificial intelligence); C4240 (Programming
		  and algorithm theory)",
  corpsource	= "Dept. of Comput. Sci., Maryland Univ., College Park, MD,
		  USA",
  journalabr	= "Inf Process Lett",
  keywords	= "15-puzzle; AI; algorithm theory; Algorithms; backward
		  search; bidirectional heuristic search algorithms;
		  Bidirectional Search; Computer Programming; execution time;
		  forward search; front-to-front algorithm; Heuristic Search;
		  limited resources; problem solving; search fronts; search
		  problems; solution quality; state space problem",
  treatment	= "T Theoretical or Mathematical"
}

@Article{	  hmm92,
  author	= "Othar Hansson and A. E. Mayer and Moti Yung",
  year		= 1992,
  title		= "Criticizing solutions to relaxed models yields powerful
		  admissible heuristics",
  journal	= "Information Sciences",
  volume	= 63,
  number	= 3,
  month		= sep,
  pages		= "207--227"
}

@Article{	  hnr68,
  author	= "Peter E. Hart and Nils J. Nilsson and Bertram Raphael",
  year		= 1968,
  title		= "A formal basis for the heuristic determination of minimum
		  cost paths",
  journal	= "IEEE Transactions on Systems Science and Cybernetics",
  volume	= "SSC-4",
  number	= 2,
  pages		= "100--107"
}

@InProceedings{	  hof00,
  author	= "M. Hoffmann",
  title		= "{Push}-$*$ is {NP}-hard",
  booktitle	= "Proceedings of the 12th Canadian Conference on
		  Computational Geometry",
  address	= "Fredericton, New Brunswick, Canada",
  year		= 2000,
  month		= aug,
  pages		= "205--209"
}

@InProceedings{	  hol87,
  author	= "Gerard J. Holzmann",
  title		= "On Limits and Possibilities of Automated Protocol
		  Analysis",
  editor	= "H. Rudin and C. West",
  booktitle	= "Proceedings of the 7th International Conference Protocol
		  Specification, Testing, and Verification",
  month		= jun,
  address	= "Zürich",
  pages		= "339--346",
  publisher	= "North-Holland Publ. Co., Amsterdam",
  year		= 1987
}

@TechReport{	  hs01,
  author	= "Markus Holzer and Stefan Schwoon",
  title		= "Assembling Molecules in {Atomix} is Hard",
  number	= "TUM-I0101",
  institution	= "Institut für Informatik, Technische Universität München",
  month		= may,
  year		= 2001
}

@Article{	  joh79,
  author	= "William Woolsey Johnson and William E. Story",
  title		= "Notes on the 15-puzzle",
  volume	= 2,
  journal	= "American Journal of Mathematics",
  year		= 1879,
  pages		= "397--404"
}

@Article{	  js00,
  author	= "Andreas Junghanns and Jonathan Schaeffer",
  title		= "Sokoban: A Case-Study in the Application of Domain
		  Knowledge in General Search Enhancements to Increase
		  Efficiency in Single-Agent Search",
  journal	= "Artificial Intelligence, special issue on search",
  year		= 2000
}

@PhDThesis{	  jun99,
  author	= "Andreas Junghanns",
  title		= "Pushing the Limits: New Developments in Single-Agent
		  Search",
  school	= "University of Alberta",
  year		= 1999
}

@Article{	  kf01,
  author	= "Richard E. Korf and Ariel Felner",
  title		= "Disjoint pattern database heuristics",
  journal	= "Artificial Intelligence Journal",
  volume	= 134,
  pages		= "9--22",
  year		= "2001"
}

@InProceedings{	  ki94*394,
  author	= "Jürgen Eckerle",
  title		= "An Optimal Bidirectional Search Algorithm",
  pages		= "394--394",
  isbn		= "3-540-58467-6",
  editor	= "Bernhard Nebel and Leonie Dreschler-Fischer",
  booktitle	= "Proceedings of the 18th German Annual Conference on
		  Artificial Intelligence: {KI}-94: Advances in Artificial
		  Intelligence",
  month		= sep,
  series	= "LNAI",
  volume	= 861,
  publisher	= "Springer, Berlin",
  year		= 1994
}

@Article{	  kk97,
  author	= "Hermann Kaindl and Gerhard Kainz",
  title		= "Bidirectional Heuristic Search Reconsidered",
  journal	= "Journal of Artificial Intelligence Research",
  volume	= 7,
  pages		= "283--317",
  year		= 1997
}

@Article{	  kor85,
  author	= "Richard E. Korf",
  title		= "Depth-First Iterative-Deepening: An Optimal Admissible
		  Tree Search",
  journal	= "Artificial Intelligence",
  volume	= 27,
  number	= 1,
  year		= 1985,
  pages		= "97--109",
  note		= "Reprinted in Chapter 6 of P.G. Raeth, editors, {\it Expert
		  Systems, A Software Methodology for Modern Applications\/},
		  pages 380--389, 1990. IEEE Computer Society Press,
		  Washington D.C..",
  avcode	= "available -- EPFL"
}

@InProceedings{	  kor97,
  author	= "Richard E. Korf",
  title		= "Finding Optimal Solutions to {Rubik's} Cube Using Pattern
		  Databases",
  pages		= "700--705",
  isbn		= "0-262-51095-2",
  booktitle	= "Proceedings of the 14th National Conference on Artificial
		  Intelligence and the 9th Conference on Innovative
		  Applications of Artificial Intelligence (AAAI-97/IAAI-97)",
  month		= jul # "~27--31",
  publisher	= "AAAI Press, Menlo Park, CA, USA",
  year		= 1997
}

@InProceedings{	  kor99,
  author	= "Richard E. Korf",
  title		= "Divide-And-Conquer Bidirectional Search: {First} Results",
  booktitle	= "IJCAI",
  pages		= "1184--1191",
  year		= 1999
}

@InProceedings{	  kt96,
  author	= "Richard E. Korf and Larry A. Taylor",
  title		= "Finding Optimal Solutions to the {Twenty-Four Puzzle}",
  pages		= "1202--1207",
  isbn		= "0-262-51091-X",
  booktitle	= "Proceedings of the 13th National Conference on Artificial
		  Intelligence and the 8th Conference on Innovative
		  Applications of Artificial Intelligence (AAAI-96/IAAI-96)",
  month		= aug # "~4--8",
  publisher	= "AAAI Press/MIT Press, Menlo Park, CA, USA",
  year		= 1996
}

@Article{	  kuh55,
  author	= "Harold W. Kuhn",
  title		= "The {Hungarian} Method for the Assignment Problem",
  journal	= "Naval Research Logistics Quarterly",
  volume	= 2,
  number	= 1,
  year		= 1955,
  pages		= "83--98"
}

@InProceedings{	  mi98,
  author	= "Teruhisa Miura and Toru Ishida",
  title		= "Stochastic Node Caching for Memory-Bounded Search",
  booktitle	= "Proceedings of the 15th National Conference on Artificial
		  Intelligence and the 10th Conference on Innovative
		  Applications of Artificial Intelligence (AAAI-98/IAAI-98)",
  pages		= "450--456",
  isbn		= "0-262-51098-7",
  month		= jul # "~26--30",
  publisher	= "AAAI Press, Menlo Park, CA, USA",
  year		= 1998
}

@Book{		  pea84,
  author	= "Judea Pearl",
  address	= "Reading, MA",
  title		= "Heuristics",
  publisher	= "Addison-Wesley",
  year		= 1984
}

@Article{	  rm94,
  author	= "Alexander Reinefeld and T. Anthony Marsland",
  title		= "Enhanced Iterative-Deepening Search",
  journal	= "IEEE Transactions on Pattern Analysis and Machine
		  Intelligence",
  volume	= 16,
  number	= 7,
  pages		= "701­-710",
  month		= jul,
  year		= 1994
}

@TechReport{	  rou99,
  author	= "Joseph O'Rourke and {The Smith Problem Solving Group}",
  title		= "{PushPush} is {NP}-hard in {3D}",
  number	= 064,
  institution	= "Smith College, Northampton, MA",
  month		= nov,
  year		= 1999
}

@InProceedings{	  rw86,
  author	= "Daniel Ratner and Manfred K. Warmuth",
  year		= 1986,
  title		= "Finding a shortest solution for the $n \times n$ extension
		  of the 15-puzzle is intractable",
  booktitle	= "Proceedings of the 5th National Conference on Artificial
		  Intelligence (AAAI-86)",
  address	= "Philadelphia, Pennsylvania",
  publisher	= "Morgan Kaufmann",
  month		= aug,
  volume	= 1,
  pages		= "168--172"
}

@Article{	  rw90,
  author	= "Daniel Ratner and Manfred K. Warmuth",
  title		= "The $(n^2-1)$-puzzle and related relocation problems",
  journal	= "Journal of Symbolic Computation",
  volume	= 10,
  number	= 2,
  pages		= "111--137",
  month		= aug,
  year		= 1990,
  coden		= "JSYCEH",
  issn		= "0747-7171",
  mrclass	= "68T20 (68Q25 68U05)",
  mrnumber	= "91i:68138",
  bibdate	= "Sat May 10 15:54:09 MDT 1997",
  acknowledgement=ack-nhfb,
  classcodes	= "C1160 (Combinatorial mathematics); C4240 (Programming and
		  algorithm theory); C4130 (Interpolation and function
		  approximation); C7310 (Mathematics)",
  corpsource	= "California Univ., Santa Cruz, CA, USA",
  keywords	= "15-puzzle; 8-puzzle; approximation algorithm;
		  approximation theory; computational complexity; heuristic
		  search; NP-hard; polynomials; problems; relocation
		  problems; robotics; search problems; search techniques;
		  symbol manipulation; techniques",
  treatment	= "P Practical; T Theoretical or Mathematical",
  xxtitle	= "Nx{N} Puzzle and Related Relocation Problem"
}

@Article{	  sav70,
  author	= "Walter J. Savitch",
  title		= "Relationships between Nondeterministic and Deterministic
		  Tape complexities",
  journal	= "Journal of Computer and System Sciences",
  month		= apr,
  volume	= 4,
  number	= 2,
  pages		= "177--192",
  year		= 1970
}

@InProceedings{	  sd96,
  author	= "Ulrich Stern and David L. Dill",
  title		= "Combining State Space Caching and Hash Compaction",
  booktitle	= "Methoden des Entwurfs und der Verifikation digitaler
		  Systeme, 4. GI/ITG/GME Workshop",
  pages		= "81--90",
  address	= "Kreischa",
  editor	= "Bernd Straube and Jens Schoenherr",
  publisher	= "Shaker Verlag, Aachen",
  series	= "Berichte aus der Informatik",
  year		= 1996,
  month		= mar
}

@InProceedings{	  tay93,
  author	= "Larry A. Taylor and Richard E. Korf",
  title		= "Pruning Duplicate Nodes in Depth-First Search",
  pages		= "756--761",
  isbn		= "0-262-51071-5",
  booktitle	= "Proceedings of the 11th National Conference on Artificial
		  Intelligence (AAAI-93)",
  month		= jul,
  publisher	= "AAAI Press, Menlo Park, CA, USA",
  year		= 1993
}

@InProceedings{	  wil88,
  author	= "Gordon T. Wilfong",
  title		= "Motion Planning in the Presence of Movable Obstacles",
  year		= 1988,
  booktitle	= "Proceedings of the Fourth Annual Symposium on
		  Computational Geometry",
  address	= "Urbana-Champaign, {IL}",
  publisher	= "ACM Press, New York",
  month		= jun # "~6--8",
  pages		= "279--288"
}

@InProceedings{	  wl93,
  author	= "Pierre Wolper and Dennis Leroy",
  title		= "Reliable Hashing Without Collision Detection",
  booktitle	= "Proceedings of the 5th International Conference on
		  Computer Aided Verification (CAV-93)",
  volume	= 7,
  pages		= "59--70",
  publisher	= "Springer, Berlin",
  year		= 1993
}