Name
Abstract | ||
|---|---|---|
We analyze the complexity of the restrictions of linear arrangement problems that are obtained if the legal permutations of the nodes are restricted to those that can be obtained by orderings of a binary tree structuring the nodes of the graph, the so-called p-tree. These versions of the linear arrangement problems occur in several places in current circuit layout systems. There the p-tree is the result of a recursive partitioning process of the graph. We show that the MINCUT LINEAR ARRANGEMENT problem and the OPTIMAL LINEAR ARRANGEMENT problem can be solved in polynomial time, if the p-tree is balanced. All other versions of the linear arrangement problems we analyzed are NP-complete. |
Year | DOI | Venue |
|---|---|---|
1988 | 10.1007/BF01928924 | Zeitschrift für Operations-Research |
Keywords | Field | DocType |
linear arrangement, dynamic programming, NP-completeness, Linear Arrangement, dynamische Programmierung, NP-Vollständigkeit | Discrete mathematics,Dynamic programming,Graph,Combinatorics,Permutation,Binary tree,Recursive partitioning,Structuring,Time complexity,Recursion,Mathematics | Journal |
Volume | Issue | ISSN |
32 | 3 | 1432-5217 |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| T. Lengauer | 1 | 110 | 15.00 |
| R. Mtiller | 2 | 0 | 0.34 |