We discuss different variants of linear arrangement problems from a parameterized perspective. More specifically, we concentrate on developing simple search tree algorithms for these problems. Despite this simplicity, the analysis of the algorithms is often rather intricate. For the newly introduced problem LINEAR ARRANGEMENT BY DELETING EDGES, we also show how to derive a small problem kernel. (C) 2008 Elsevier B.V. All rights reserved.
展开▼
