Discrete Applied Mathematics, Volume 153

Volume 153, Numbers 1-3, 1 December 2005

• Lefteris M. Kirousis, Evangelos Kranakis:
  Special Issue on Typical Case Complexity and Phase Transitions. 1
  Electronic Edition (link) BibTeX
• Adam Beacham, Joseph C. Culberson:
  On the complexity of unfrozen problems. 3-24
  Electronic Edition (link) BibTeX
• Paul Beame, Joseph C. Culberson, David G. Mitchell, Cristopher Moore:
  The resolution complexity of random graph k-colorability. 25-47
  Electronic Edition (link) BibTeX
• Nadia Creignou, Hervé Daudé, John V. Franco:
  A sharp threshold for the renameable-Horn and the q-Horn properties. 48-57
  Electronic Edition (link) BibTeX
• Tassos Dimitriou:
  SAT distributions with planted assignments and phase transitions between decision and optimization problems. 58-72
  Electronic Edition (link) BibTeX
• András Faragó:
  On the typical case complexity of graph optimization. 73-88
  Electronic Edition (link) BibTeX
• John V. Franco:
  Typical case complexity of Satisfiability Algorithms and the threshold phenomenon. 89-123
  Electronic Edition (link) BibTeX
• Yong Gao, Joseph C. Culberson:
  Resolution complexity of random constraint satisfaction problems: Another half of the story. 124-140
  Electronic Edition (link) BibTeX
• Gabriel Istrate:
  Threshold properties of random boolean constraint satisfaction problems. 141-152
  Electronic Edition (link) BibTeX
• Ulrich Voll:
  A novel giant-subgraph phase-transition in sparse random k-partite graphs. 153-181
  Electronic Edition (link) BibTeX