test Browse by Author Names Browse by Titles of Works Browse by Subjects of Works Browse by Issue Dates of Works
       

Advanced Search
Home   
 
Browse   
Communities
& Collections
  
Issue Date   
Author   
Title   
Subject   
 
Sign on to:   
Receive email
updates
  
My Account
authorized users
  
Edit Profile   
 
Help   
About T-Space   

T-Space at The University of Toronto Libraries >
University of Toronto at Scarborough >
Computer and Mathematical Science >
Mathematics >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1807/9461

Title: Models for random constraint satisfaction problems
Authors: Molloy, M.
Keywords: Constraint satisfaction problems
Random models
Sharp threshold
Threshold
Issue Date: 2003
Publisher: Society for Industrial and Applied Mathematics
Citation: Molloy, M. (2003). Models for random constraint satisfaction problems. SIAM Journal on Computing, 32(4), 935-949
Abstract: We introduce a class of models for random constraint satisfaction problems. This class includes and generalizes many previously studied models. We characterize those models from our class which are asymptotically interesting in the sense that the limiting probability of satisfiability changes significantly as the number of constraints increases. We also discuss models which exhibit a sharp threshold for satisfiability in the sense that the limiting probability jumps from 0 to 1 suddenly as the number of constraints increases.
Description: © 2003 SIAM. All rights reserved.
URI: http://hdl.handle.net/1807/9461
Rights: IMPORTANT NOTICE: TO USERS OF THIS DATA ALL DATA WAS COLLECTED THROUGH THE CONSIDERABLE EFFORTS OF THE RESEARCHERS CONTRIBUTING TO IT. WHILE THE DATA CAN BE USED FOR NEW ANALYSES, Contact should be main to the collector of this data prior to publication and ACKNOWLEDGEMENT MUST BE EXPLICITLY MADE AS TO THE COLLECTOR AND CONTRIBUTOR OF THESE DATA.
Appears in Collections:Mathematics

Files in This Item:

File Description SizeFormat
post print-models of random constraint....pdf234.73 kBAdobe PDF
View/Open

Items in T-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

uoft