Complexity of constraint satisfaction problems (Record no. 358240)

000 -LEADER
fixed length control field 02156ntm a22002417a 4500
003 - CONTROL NUMBER IDENTIFIER
control field AT-ISTA
005 - DATE AND TIME OF LATEST TRANSACTION
control field 20190813102206.0
008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION
fixed length control field 170609s2017 au ||||| m||| 00| 0 eng d
040 ## - CATALOGING SOURCE
Transcribing agency IST
100 ## - MAIN ENTRY--PERSONAL NAME
Personal name Rolinek, Michal
9 (RLIN) 3357
245 ## - TITLE STATEMENT
Title Complexity of constraint satisfaction problems
260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT)
Name of publisher, distributor, etc. IST Austria
Date of publication, distribution, etc. 2017
500 ## - GENERAL NOTE
General note Thesis
505 ## - FORMATTED CONTENTS NOTE
Formatted contents note Acknowledgments
505 ## - FORMATTED CONTENTS NOTE
Formatted contents note Abstract
505 ## - FORMATTED CONTENTS NOTE
Formatted contents note 1 Introduction
505 ## - FORMATTED CONTENTS NOTE
Formatted contents note 2 Complexity of valued CSP
505 ## - FORMATTED CONTENTS NOTE
Formatted contents note 3 Generalizing Edmonds' algorithm
505 ## - FORMATTED CONTENTS NOTE
Formatted contents note A Appendices
520 ## - SUMMARY, ETC.
Summary, etc. An instance of the Constraint Satisfaction Problem (CSP) is given by a finite set of<br/>variables, a finite domain of labels, and a set of constraints, each constraint acting on<br/>a subset of the variables. The goal is to find an assignment of labels to its variables<br/>that satisfies all constraints (or decide whether one exists). If we allow more general<br/>“soft” constraints, which come with (possibly infinite) costs of particular assignments,<br/>we obtain instances from a richer class called Valued Constraint Satisfaction Problem<br/>(VCSP). There the goal is to find an assignment with minimum total cost.<br/>In this thesis, we focus (assuming that P<br/>6<br/>=<br/>NP) on classifying computational com-<br/>plexity of CSPs and VCSPs under certain restricting conditions. Two results are the core<br/>content of the work. In one of them, we consider VCSPs parametrized by a constraint<br/>language, that is the set of “soft” constraints allowed to form the instances, and finish<br/>the complexity classification modulo (missing pieces of) complexity classification for<br/>analogously parametrized CSP. The other result is a generalization of Edmonds’ perfect<br/>matching algorithm. This generalization contributes to complexity classfications in two<br/>ways. First, it gives a new (largest known) polynomial-time solvable class of Boolean<br/>CSPs in which every variable may appear in at most two constraints and second, it<br/>settles full classification of Boolean CSPs with planar drawing (again parametrized by a<br/>constraint language).
856 ## - ELECTRONIC LOCATION AND ACCESS
Uniform Resource Identifier <a href="https://doi.org/10.15479/AT:ISTA:th_815">https://doi.org/10.15479/AT:ISTA:th_815</a>
942 ## - ADDED ENTRY ELEMENTS (KOHA)
Source of classification or shelving scheme
Holdings
Withdrawn status Lost status Source of classification or shelving scheme Damaged status Not for loan Permanent Location Current Location Date acquired Barcode Date last seen Price effective from Koha item type
  Not Lost       Library Library 2017-06-09 AT-ISTA#001356 2018-11-06 2017-06-09 Book

Powered by Koha