AbstractThe Consistent Labeling Problem is of considerable importance in Artificial Intelligence, Operations Research and Symbolic Logic. It has received much attention, but most work has addressed the specialized binary form of the problem Furthermore, none of the relatively notion, but most work has addressed the specialized binary form of the problem Furthermore, none of the relatively few papers that treat the general problem have dealt analytically with the issue of complexity. In this paper we present two algorithms for solving the general Consistent Labeling Problem and for each of these the expected complexity is given under a simple statistical model for the distribution of problems. This model is sufficient to expose certain interesting aspects of complexity for the two algorithms. Work currently in progress will address more subtle aspects by extension to more refined statistical models.
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).