Linear arrangement problems on recursively partitioned graphs

DOI10.1007/BF01928924zbMath0637.90073OpenAlexW1979073798MaRDI QIDQ3778551

Rolf Muller, Thomas Lengauer

Publication date: 1988

Published in: Zeitschrift für Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01928924

zbMATH Keywords

binary treeNP-completepolynomial timecircuit layout systemsp-treerestrictions of linear arrangement problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)

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

This page was built for publication: Linear arrangement problems on recursively partitioned graphs