Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
Articles 1 - 3 of 3
Full-Text Articles in Physical Sciences and Mathematics
Relational Neighborhood Inverse Consistency For Constraint Satisfaction, Robert J. Woodward, Shant Karakashian, Berthe Y. Choueiry, Christian Bessiere
Relational Neighborhood Inverse Consistency For Constraint Satisfaction, Robert J. Woodward, Shant Karakashian, Berthe Y. Choueiry, Christian Bessiere
CSE Technical Reports
Freuder and Elfe [1996] introduced Neighborhood Inverse Consistency (NIC) as a new local consistency property for Constraint Satisfaction Problems (CSPs) that filters the domains of variables. Two advantages of the algorithm for enforcing NIC is that it automatically adapts its filtering power to the local connectivity of the network and has insignificant space overhead. In this document, we discuss Relational Neighborhood Inverse Consistency (RNIC), which is an extension of NIC to filter relations introduced in [Woodward et al., 2011a], how we enhance the propagation effectiveness by reformulating the dual graph of the CSP. We also describe an automated selection policy …
Isomorph-Free Generation Of 2-Connected Graphs With Applications, Derrick Stolee
Isomorph-Free Generation Of 2-Connected Graphs With Applications, Derrick Stolee
CSE Technical Reports
Many interesting graph families contain only 2-connected graphs, which have ear decompositions. We develop a technique to generate families of unlabeled 2-connected graphs using ear augmentations and apply this technique to two problems. In the first application, we search for uniquely Kr-saturated graphs and find the list of uniquely K4-saturated graphs on at most 12 vertices, supporting current conjectures for this problem. In the second application, we verify the Edge Reconstruction Conjecture for all 2-connected graphs on at most 12 vertices. This technique can be easily extended to more problems concerning 2-connected graphs.
Propeller: A Scalable Metadata Organization For A Versatile Searchable File System, Lei Xu, Hong Jiang, Xue Liu, Lei Tian, Yu Hua, Jian Hu
Propeller: A Scalable Metadata Organization For A Versatile Searchable File System, Lei Xu, Hong Jiang, Xue Liu, Lei Tian, Yu Hua, Jian Hu
CSE Technical Reports
The exponentially increasing amount of data in file systems has made it increasingly important for users, administrators and applications to be able to fast retrieve files using file-search services, instead of replying on the standard file system API to traverse the hierarchical namespaces. The quality of the file-search services is significantly affected by the file-indexing overhead, the file-search performance and the accuracy of search results. Unfortunately, the existing file-search solutions either are so poorly scalable that their performance degrades unacceptably when the systems scale up, or incur so much crawling delays that they produce acceptably inaccurate results. We believe that …