[an error occurred while processing this directive]<meta name="keywords" content="Department of Computer Science, publications, by type, Constraint Satisfaction for Configuration: Logical Fundamentals, Algorithms, and Complexity"></meta><meta name="description" content="Publications, by type,Constraint Satisfaction for Configuration: Logical Fundamentals, Algorithms, and Complexity, Department of Computer Science, Oxford"></meta><title>Department of Computer Science: Constraint Satisfaction for Configuration: Logical Fundamentals, Algorithms, and Complexity: Publications
</title><style type="text/css">
			  .btn-toolbar::after, .btn-toolbar::before
			  {
			    content: " ";
			    display: table;
			  }

			
			.btn-toolbar
			{
			    margin-bottom: 2em;
			}

			  .btn-toolbar::after, .btn-group::after
			  {
			    clear: both;
			  }


			.btn-toolbar .btn, .btn-toolbar .btn-group
			  {
			    float: left;
			}
			
			.btn-group
			  {
			    display: inline-block;
			    position: relative;
			    vertical-align: middle;
			}

			  .btn-group > .btn:first-child:not(:last-child)
			  {
			    border-bottom-right-radius: 0;
			    border-top-right-radius: 0;
			}
			
			.btn-group > .btn:first-child
			  {
			    margin-left: 0;
			}

			.btn-group > .btn
			  {
			    float: left;
			    position: relative;
			}

			  .btn-group > .btn:not(:first-child):not(:last-child)
			  {
			    border-radius: 0;
			}
			
			  .btn-group > .btn:last-child:not(:first-child)
			  {
			    border-bottom-left-radius: 0;
			    border-top-left-radius: 0;
			}
			
			.btn-group .btn + .btn, .btn-group .btn + .btn-group, .btn-group .btn-group + .btn, .btn-group .btn-group + .btn-group
			  {
			    margin-left: -2px;
			}
			</style>[an error occurred while processing this directive]<div class="content-width"><ol class="breadcrumb text-uppercase"><li><a href="/">Home</a></li><li><a href="/research/">Research</a></li><li><a href="/research/dk/">Data, Knowledge and Action</a></li><li><a href="/research/dk/projects.html">projects</a></li><li><a href="/projects/ConstraintSatisfaction/">Constraint Satisfaction for Configuration: Logical Fundamentals, Algorithms, and Complexity</a></li><li class="active">Publications</li></ol></div><!-- MOBILE NAVIGATION --><div class="content-width space-below mobile-menu-placeholder visible-xs visible-sm"></div><!-- COLUMNS --><div class="container-fluid content-width"><div class="row"><div class="col-xs-12 col-md-9 col-md-push-3" id="maincontent"><!-- CONTENT (Column 2) --><div class="page-title"><h1>Constraint Satisfaction for Configuration: Logical Fundamentals, Algorithms, and Complexity: Publications
</h1></div><div role="toolbar" class="btn-toolbar"><div class="btn-group"><a href="/projects/publications/date/ConstraintSatisfaction.html" aria-hidden="true" type="button" class="btn btn-default"><span class="glyphicon glyphicon-sort-by-attributes"></span> By date</a><a href="/projects/publications/title/ConstraintSatisfaction.html" aria-hidden="true" type="button" class="btn btn-default"><span class="glyphicon glyphicon-sort-by-attributes"></span> By title</a><a href="/projects/publications/type/ConstraintSatisfaction.html" aria-hidden="true" type="button" class="btn btn-oxford-blue"><span class="glyphicon glyphicon-sort-by-attributes"></span> By type</a><a href="/projects/publications/bibtex/ConstraintSatisfaction.html" aria-hidden="true" type="button" class="btn btn-default"><span class="glyphicon glyphicon-file"></span> BibTex</a></div></div><h2>
      Journal papers
      </h2><ul class="list-unbulleted list-unbulleted-spaced"><li>
	
	<div class="row">
		
			<div class="col-xs-1 text-right">
				[1] 
			</div>

		
        
		<div
			class="col-xs-11"
		>
			
	
	<p class="publicationTitle"> <strong>
            Size and Treewidth Bounds for Conjunctive Queries </strong> </p>
	    <p class="publicationAuthors"> <em> Georg Gottlob&#x201a; Stephanie Tien Lee&#x201a; Gregory Valiant and Paul Valiant  </em> </p>
	
	<p class="publicationDetails"> 
        In <em>Journal of the ACM</em>.
        2012.
        </p> <p
            class="publicationNote"> Accepted for publication</p>
	
        		<p class="publicationlinks"> <a
        
            		href="/publications/publication6310-abstract.html">
			Details <span class="sr-only" > about <em> Size and Treewidth Bounds for Conjunctive Queries  </em></span> </a> |
			<a href="/publications/publication6310.bib">
			BibTeX  <span class="sr-only" > data for <em> Size and Treewidth Bounds for Conjunctive Queries  </em></span>   </a>
			
			

				     |
                			<a 
                			    href="http://www.cs.ox.ac.uk/files/5024/GLVV_7_11_conjqueries_jacm.pdf">Download
					     (pdf)

					    <span class="sr-only" > of <em> Size and Treewidth Bounds for Conjunctive Queries  </em></span>

					    </a>


				    
		
		</div> 
	</div> 
	
        </li><li>
	
	<div class="row">
		
			<div class="col-xs-1 text-right">
				[2] 
			</div>

		
        
		<div
			class="col-xs-11"
		>
			
	
	<p class="publicationTitle"> <strong>
            On Minimal Constraint Networks </strong> </p>
	    <p class="publicationAuthors"> <em> Georg Gottlob  </em> </p>
	
	<p class="publicationDetails"> 
        In <em>Artificial Intelligence</em>.
        2012.
        </p> <p
            class="publicationNote"> Submitted Preprint</p>
	
        		<p class="publicationlinks"> <a
        
            		href="/publications/publication6076-abstract.html">
			Details <span class="sr-only" > about <em> On Minimal Constraint Networks  </em></span> </a> |
			<a href="/publications/publication6076.bib">
			BibTeX  <span class="sr-only" > data for <em> On Minimal Constraint Networks  </em></span>   </a>
			
			

				     |
                			<a 
                			    href="http://www.cs.ox.ac.uk/files/4802/GottlobMinimalAIJ.pdf">Download
					     (pdf)

					    <span class="sr-only" > of <em> On Minimal Constraint Networks  </em></span>

					    </a>


				    
		
		</div> 
	</div> 
	
        </li></ul><h2>
      Conference papers
      </h2><ul class="list-unbulleted list-unbulleted-spaced"><li>
	
	<div class="row">
		
			<div class="col-xs-1 text-right">
				[1] 
			</div>

		
        
		<div
			class="col-xs-11"
		>
			
	
	<p class="publicationTitle"> <strong>
            The Partner Units Problem &#x2212; A Constraint Programming Case Study </strong> </p>
	    <p class="publicationAuthors"> <em> Conrad Drescher  </em> </p>
	
	<p class="publicationDetails"> 
            In  
            <em>
            Proceedings of the 24th IEEE International Conference on Tools with Artificial Intelligence&#x201a; ICTAI'12</em>.
        2012.
        </p>
	
        		<p class="publicationlinks"> <a
        
            		href="/publications/publication6234-abstract.html">
			Details <span class="sr-only" > about <em> The Partner Units Problem &#x2212; A Constraint Programming Case Study  </em></span> </a> |
			<a href="/publications/publication6234.bib">
			BibTeX  <span class="sr-only" > data for <em> The Partner Units Problem &#x2212; A Constraint Programming Case Study  </em></span>   </a>
			
			

				     |
                			<a 
                			    href="http://www.cs.ox.ac.uk/files/4906/ictai.pdf">Download
					     (pdf)

					    <span class="sr-only" > of <em> The Partner Units Problem &#x2212; A Constraint Programming Case Study  </em></span>

					    </a>


				    
		
		</div> 
	</div> 
	
        </li><li>
	
	<div class="row">
		
			<div class="col-xs-1 text-right">
				[2] 
			</div>

		
        
		<div
			class="col-xs-11"
		>
			
	
	<p class="publicationTitle"> <strong>
            Unifying Software and Product Configuration: A Research Roadmap </strong> </p>
	    <p class="publicationAuthors"> <em> Arnaud Hubaux&#x201a; Dietmar Jannach&#x201a; Conrad Drescher&#x201a; Leonardo Murta&#x201a; Tomi Mannisto&#x201a; Krzysztof Czarnecki&#x201a; Patrick Heymans&#x201a; Tien Nguyen and Markus Zanker  </em> </p>
	
	<p class="publicationDetails"> 
            In  
            <em>
            Proceedings of the ECAI 2012 Workshop on Configuration</em>.
        2012.
        </p>
	
        		<p class="publicationlinks"> <a
        
            		href="/publications/publication6185-abstract.html">
			Details <span class="sr-only" > about <em> Unifying Software and Product Configuration: A Research Roadmap  </em></span> </a> |
			<a href="/publications/publication6185.bib">
			BibTeX  <span class="sr-only" > data for <em> Unifying Software and Product Configuration: A Research Roadmap  </em></span>   </a>
			
			

				     |
                			<a 
                			    href="http://www.cs.ox.ac.uk/files/4853/confws12.pdf">Download
					     (pdf)

					    <span class="sr-only" > of <em> Unifying Software and Product Configuration: A Research Roadmap  </em></span>

					    </a>


				    
		
		</div> 
	</div> 
	
        </li><li>
	
	<div class="row">
		
			<div class="col-xs-1 text-right">
				[3] 
			</div>

		
        
		<div
			class="col-xs-11"
		>
			
	
	<p class="publicationTitle"> <strong>
            LoCo &#x2014; A Logic for Configuration Problems </strong> </p>
	    <p class="publicationAuthors"> <em> Markus Aschinger&#x201a; Conrad Drescher and Heribert Vollmer  </em> </p>
	
	<p class="publicationDetails"> 
            In  
            <em>
            Proceedings of the 20th European Conference on Artificial Intelligence&#x201a; ECAI 2012</em>.
        2012.
        </p>
	
        		<p class="publicationlinks"> <a
        
            		href="/publications/publication6135-abstract.html">
			Details <span class="sr-only" > about <em> LoCo &#x2014; A Logic for Configuration Problems  </em></span> </a> |
			<a href="/publications/publication6135.bib">
			BibTeX  <span class="sr-only" > data for <em> LoCo &#x2014; A Logic for Configuration Problems  </em></span>   </a>
			
			

				     |
                			<a 
                			    href="http://www.cs.ox.ac.uk/files/4821/locoecai2012.pdf">Download
					     (pdf)

					    <span class="sr-only" > of <em> LoCo &#x2014; A Logic for Configuration Problems  </em></span>

					    </a>


				    
		
		</div> 
	</div> 
	
        </li><li>
	
	<div class="row">
		
			<div class="col-xs-1 text-right">
				[4] 
			</div>

		
        
		<div
			class="col-xs-11"
		>
			
	
	<p class="publicationTitle"> <strong>
            Parameterized Complexity of Weighted Satisfiability Problems </strong> </p>
	    <p class="publicationAuthors"> <em> Nadia Creignou and Heribert Vollmer  </em> </p>
	
	<p class="publicationDetails"> 
            In  
            <em>
            Proceedings of the 15th International Conference on Theory and Applications of Satisfiability Testing&#x201a; SAT 2012</em>.
        2012.
        </p>
	
        		<p class="publicationlinks"> <a
        
            		href="/publications/publication6086-abstract.html">
			Details <span class="sr-only" > about <em> Parameterized Complexity of Weighted Satisfiability Problems  </em></span> </a> |
			<a href="/publications/publication6086.bib">
			BibTeX  <span class="sr-only" > data for <em> Parameterized Complexity of Weighted Satisfiability Problems  </em></span>   </a>
			
			

				     |
                			<a 
                			    href="http://www.cs.ox.ac.uk/files/4803/VollmerCreignouSAT12.pdf">Download
					     (pdf)

					    <span class="sr-only" > of <em> Parameterized Complexity of Weighted Satisfiability Problems  </em></span>

					    </a>


				    
		
		</div> 
	</div> 
	
        </li><li>
	
	<div class="row">
		
			<div class="col-xs-1 text-right">
				[5] 
			</div>

		
        
		<div
			class="col-xs-11"
		>
			
	
	<p class="publicationTitle"> <strong>
            On Minimal Constraint Networks </strong> </p>
	    <p class="publicationAuthors"> <em> Georg Gottlob  </em> </p>
	
	<p class="publicationDetails"> 
            In  
            <em>
            Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming&#x201a; CP 2011</em>.
        Perugia&#x201a; Italy.
        2011.
        </p>
	
        		<p class="publicationlinks"> <a
        
            		href="/publications/publication5751-abstract.html">
			Details <span class="sr-only" > about <em> On Minimal Constraint Networks  </em></span> </a> |
			<a href="/publications/publication5751.bib">
			BibTeX  <span class="sr-only" > data for <em> On Minimal Constraint Networks  </em></span>   </a>
			
			

				     |
                			<a 
                			    href="http://www.cs.ox.ac.uk/files/4439/GottlobMinimalCP11.pdf">Download
					     (pdf)

					    <span class="sr-only" > of <em> On Minimal Constraint Networks  </em></span>

					    </a>


				    
		
		</div> 
	</div> 
	
        </li><li>
	
	<div class="row">
		
			<div class="col-xs-1 text-right">
				[6] 
			</div>

		
        
		<div
			class="col-xs-11"
		>
			
	
	<p class="publicationTitle"> <strong>
            Introducing LoCo&#x201a; a Logic for Configuration Problems </strong> </p>
	    <p class="publicationAuthors"> <em> Markus Aschinger&#x201a; Conrad Drescher and Georg Gottlob  </em> </p>
	
	<p class="publicationDetails"> 
            In  
            <em>
            Proceedings of the 2nd Workshop on Logics for Component Configuration&#x201a; LoCoCo 2011</em>.
        Perugia&#x201a; Italy.
        2011.
        </p>
	
        		<p class="publicationlinks"> <a
        
            		href="/publications/publication5347-abstract.html">
			Details <span class="sr-only" > about <em> Introducing LoCo&#x201a; a Logic for Configuration Problems  </em></span> </a> |
			<a href="/publications/publication5347.bib">
			BibTeX  <span class="sr-only" > data for <em> Introducing LoCo&#x201a; a Logic for Configuration Problems  </em></span>   </a>
			
			

				     |
                			<a 
                			    href="http://www.cs.ox.ac.uk/files/4171/LoCo.pdf">Download
					     (pdf)

					    <span class="sr-only" > of <em> Introducing LoCo&#x201a; a Logic for Configuration Problems  </em></span>

					    </a>


				    
		
		</div> 
	</div> 
	
        </li><li>
	
	<div class="row">
		
			<div class="col-xs-1 text-right">
				[7] 
			</div>

		
        
		<div
			class="col-xs-11"
		>
			
	
	<p class="publicationTitle"> <strong>
            Tackling the Partner Units Configuration Problem </strong> </p>
	    <p class="publicationAuthors"> <em> Markus Aschinger&#x201a; Conrad Drescher&#x201a; Georg Gottlob&#x201a; Peter Jeavons and Evgen&#x0133; Thorstensen  </em> </p>
	
	<p class="publicationDetails"> 
            In  
            <em>
            Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011)</em>.
        Barcelona&#x201a; Spain.
        2011.
        </p>
	
        		<p class="publicationlinks"> <a
        
            		href="/publications/publication4908-abstract.html">
			Details <span class="sr-only" > about <em> Tackling the Partner Units Configuration Problem  </em></span> </a> |
			<a href="/publications/publication4908.bib">
			BibTeX  <span class="sr-only" > data for <em> Tackling the Partner Units Configuration Problem  </em></span>   </a>
			
			

				     |
                			<a 
                			    href="http://www.cs.ox.ac.uk/files/3945/ijcai11.pdf">Download
					     (pdf)

					    <span class="sr-only" > of <em> Tackling the Partner Units Configuration Problem  </em></span>

					    </a>


				    
		
		</div> 
	</div> 
	
        </li><li>
	
	<div class="row">
		
			<div class="col-xs-1 text-right">
				[8] 
			</div>

		
        
		<div
			class="col-xs-11"
		>
			
	
	<p class="publicationTitle"> <strong>
            Optimization Methods for the Partner Units Problem </strong> </p>
	    <p class="publicationAuthors"> <em> Markus Aschinger&#x201a; Conrad Drescher&#x201a; Gerhard Friedrich&#x201a; Georg Gottlob&#x201a; Peter Jeavons&#x201a; Anna Ryabokon and Evgen&#x0133; Thorstensen  </em> </p>
	
	<p class="publicationDetails"> 
            In  
            <em>
            Proceedings of the 8th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2011)</em>.
        Berlin&#x201a; Germany.
        2011.
        </p>
	
        		<p class="publicationlinks"> <a
        
            		href="/publications/publication4772-abstract.html">
			Details <span class="sr-only" > about <em> Optimization Methods for the Partner Units Problem  </em></span> </a> |
			<a href="/publications/publication4772.bib">
			BibTeX  <span class="sr-only" > data for <em> Optimization Methods for the Partner Units Problem  </em></span>   </a>
			
			

				     |
                			<a 
                			    href="http://www.cs.ox.ac.uk/files/3919/cpaior.pdf">Download
					     (pdf)

					    <span class="sr-only" > of <em> Optimization Methods for the Partner Units Problem  </em></span>

					    </a>


				    
		
		</div> 
	</div> 
	
        </li><li>
	
	<div class="row">
		
			<div class="col-xs-1 text-right">
				[9] 
			</div>

		
        
		<div
			class="col-xs-11"
		>
			
	
	<p class="publicationTitle"> <strong>
            Balanced Queries: Divide and Conquer </strong> </p>
	    <p class="publicationAuthors"> <em> Dmitri Akatov and Georg Gottlob  </em> </p>
	
	<p class="publicationDetails"> 
            In  
            <em>
            Proceedings of the 35th International Symposiums on Mathematical Foundations of Computer Science (MFCS 2010)</em>.
        Brno&#x201a; Czech Republic.
        2010.
        </p>
	
        		<p class="publicationlinks"> <a
        
            		href="/publications/publication4780-abstract.html">
			Details <span class="sr-only" > about <em> Balanced Queries: Divide and Conquer  </em></span> </a> |
			<a href="/publications/publication4780.bib">
			BibTeX  <span class="sr-only" > data for <em> Balanced Queries: Divide and Conquer  </em></span>   </a>
			
			

				     |
                			<a 
                			    href="http://www.cs.ox.ac.uk/files/3916/DivideAndConquerGottlobAkatov.pdf">Download
					     (pdf)

					    <span class="sr-only" > of <em> Balanced Queries: Divide and Conquer  </em></span>

					    </a>


				    
		
		</div> 
	</div> 
	
        </li><li>
	
	<div class="row">
		
			<div class="col-xs-1 text-right">
				[10] 
			</div>

		
        
		<div
			class="col-xs-11"
		>
			
	
	<p class="publicationTitle"> <strong>
            Tractable Optimization Problems through Hypergraph&#x2212;Based Structural Restrictions </strong> </p>
	    <p class="publicationAuthors"> <em> Georg Gottlob&#x201a; Gianluigi Greco and Francesco Scarcello  </em> </p>
	
	<p class="publicationDetails"> 
            In  
            <em>
            Proceedings of the 36th International Colloquium on Automata&#x201a; Languages and Programming</em>.
        Rhodes&#x201a; Greece.
        2009.
        </p>
	
        		<p class="publicationlinks"> <a
        
            		href="/publications/publication4781-abstract.html">
			Details <span class="sr-only" > about <em> Tractable Optimization Problems through Hypergraph&#x2212;Based Structural Restrictions  </em></span> </a> |
			<a href="/publications/publication4781.bib">
			BibTeX  <span class="sr-only" > data for <em> Tractable Optimization Problems through Hypergraph&#x2212;Based Structural Restrictions  </em></span>   </a>
			
			

				     |
                			<a 
                			    href="http://www.cs.ox.ac.uk/files/3915/Gottlob%20ICALP.pdf">Download
					     (pdf)

					    <span class="sr-only" > of <em> Tractable Optimization Problems through Hypergraph&#x2212;Based Structural Restrictions  </em></span>

					    </a>


				    
		
		</div> 
	</div> 
	
        </li></ul><h2>
      Technical reports
      </h2><ul class="list-unbulleted list-unbulleted-spaced"><li>
	
	<div class="row">
		
			<div class="col-xs-1 text-right">
				[1] 
			</div>

		
        
		<div
			class="col-xs-11"
		>
			
	
	<p class="publicationTitle"> <strong>
            Tackling the Partner Units Configuration Problem </strong> </p>
	    <p class="publicationAuthors"> <em> Markus Aschinger&#x201a; Conrad Drescher&#x201a; Gerhard Friedrich&#x201a; Georg Gottlob&#x201a; Peter Jeavons&#x201a; Anna Ryabokon and Evgen&#x0133; Thorstensen  </em> </p>
	
	<p class="publicationDetails"> 
            No. CS&#x2212;RR&#x2212;10&#x2212;28.
        Computing Laboratory&#x201a; University of Oxford.
        2010.
        </p>
	
        		<p class="publicationlinks"> <a
        
            		href="/publications/publication5055-abstract.html">
			Details <span class="sr-only" > about <em> Tackling the Partner Units Configuration Problem  </em></span> </a> |
			<a href="/publications/publication5055.bib">
			BibTeX  <span class="sr-only" > data for <em> Tackling the Partner Units Configuration Problem  </em></span>   </a>
			
			

				     |
                			<a 
                			    href="http://www.cs.ox.ac.uk/files/4055/PUP_TR_10.pdf">Download
					     (pdf)

					    <span class="sr-only" > of <em> Tackling the Partner Units Configuration Problem  </em></span>

					    </a>


				    
		
		</div> 
	</div> 
	
        </li></ul><h2>
      Miscellaneous
      </h2><ul class="list-unbulleted list-unbulleted-spaced"><li>
	
	<div class="row">
		
			<div class="col-xs-1 text-right">
				[1] 
			</div>

		
        
		<div
			class="col-xs-11"
		>
			
	
	<p class="publicationTitle"> <strong>
            Structural Decomposition Methods&#x201a; and What They are Good For </strong> </p>
	    <p class="publicationAuthors"> <em> Markus Aschinger&#x201a; Conrad Drescher&#x201a; Georg Gottlob&#x201a; Peter Jeavons and Evgen&#x0133; Thorstensen  </em> </p>
	
	<p class="publicationDetails"> 2011.
        </p> <p
            class="publicationNote"> Invited Paper at STACS 2011</p>
	
        		<p class="publicationlinks"> <a
        
            		href="/publications/publication4779-abstract.html">
			Details <span class="sr-only" > about <em> Structural Decomposition Methods&#x201a; and What They are Good For  </em></span> </a> |
			<a href="/publications/publication4779.bib">
			BibTeX  <span class="sr-only" > data for <em> Structural Decomposition Methods&#x201a; and What They are Good For  </em></span>   </a>
			
			

				     |
                			<a 
                			    href="http://www.cs.ox.ac.uk/files/3918/stacs.pdf">Download
					     (pdf)

					    <span class="sr-only" > of <em> Structural Decomposition Methods&#x201a; and What They are Good For  </em></span>

					    </a>


				    
		
		</div> 
	</div> 
	
        </li></ul></div><div class="col-xs-12 col-md-3 col-md-pull-9 side-menu-col">[an error occurred while processing this directive]</div></div></div>[an error occurred while processing this directive]