Linear arrangement problems on recursively partitioned graphs
From MaRDI portal
Publication:3778551
DOI10.1007/BF01928924zbMath0637.90073MaRDI QIDQ3778551
Publication date: 1988
Published in: Zeitschrift für Operations Research (Search for Journal in Brave)
binary tree; NP-complete; polynomial time; circuit layout systems; p-tree; restrictions of linear arrangement problems
90C35: Programming involving graphs or networks
68Q25: Analysis of algorithms and problem complexity
05C05: Trees
68P10: Searching and sorting
68R10: Graph theory (including graph drawing) in computer science
90C27: Combinatorial optimization
Cites Work
- Unnamed Item
- The NP-completeness of the bandwidth minimization problem
- A polynomial algorithm for the min-cut linear arrangement of trees
- Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
- An Efficient Heuristic Procedure for Partitioning Graphs
- A Minimum Linear Arrangement Algorithm for Undirected Trees