文章基本信息

标题：Structural Decomposition Methods and What They are Good For
本地全文：下载
作者：Markus Aschinger ; Conrad Drescher ; Georg Gottlob 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2011
卷号：9
页码：12-28
DOI：10.4230/LIPIcs.STACS.2011.12
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：This paper reviews structural problem decomposition methods, such as tree and path decompositions. It is argued that these notions can be applied in two distinct ways: Either to show that a problem is efficiently solvable when a width parameter is fixed, or to prove that the unrestricted (or some width-parameter free) version of a problem is tractable by using a width-notion as a mathematical tool for directly solving the problem at hand. Examples are given for both cases. As a new showcase for the latter usage, we report some recent results on the Partner Units Problem, a form of configuration problem arising in an industrial context. We use the notion of a path decomposition to identify and solve a tractable class of instances of this problem with practical relevance.
关键词：decompositions