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

Last update Thu May 23 18:40:07 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page