On optimal linear arrangements of trees

DOI10.1016/0898-1221(84)90085-3zbMath0533.05022OpenAlexW2090666691MaRDI QIDQ789395

Fan R. K. Chung

Publication date: 1984

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0898-1221(84)90085-3

zbMATH Keywords

rooted treeslabeling of verticesoptimal linear rearrangement

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (05C99)

Related Items (24)

A Correction on Shiloach's Algorithm for Minimum Linear Arrangement of Trees ⋮ Generating lower bounds for the linear arrangement problem ⋮ On bandwidth and edgesum for the composition of two graphs ⋮ Two results on linear embeddings of complete binary trees ⋮ Minimum Linear Arrangement of the Cartesian Product of Optimal Order Graph and Path ⋮ On bipartite crossings, largest biplanar subgraphs, and the linear arrangement problem ⋮ The maximum linear arrangement problem for trees under projectivity and planarity ⋮ Routing with critical paths ⋮ A variation on the min cut linear arrangement problem ⋮ Lower and upper bounds for the linear arrangement problem on interval graphs ⋮ The scaling of the minimum sum of edge lengths in uniformly random trees ⋮ Heuristics for the data arrangement problem on regular trees ⋮ Optimal linear labelings and eigenvalues of graphs ⋮ A study on cyclic bandwidth sum ⋮ Fast geometric approximation techniques and geometric embedding problems ⋮ The bandwidth sum of join and composition of graphs ⋮ Bandwidth sums of block graphs and cacti ⋮ Optimal arrangement of data in a tree directory ⋮ Linear time algorithms to solve the linear ordering problem for oriented tree based graphs ⋮ k-Level Crossing Minimization Is NP-Hard for Trees ⋮ Optimal one-page tree embeddings in linear time ⋮ Minimum projective linearizations of trees in linear time ⋮ On minimum cuts and the linear arrangement problem ⋮ Bounds of the sum of edge lengths in linear arrangements of trees

Cites Work

• The NP-completeness of the bandwidth minimization problem
• Some simplified NP-complete graph problems
• Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees
• Complexity Results for Bandwidth Minimization
• A Minimum Linear Arrangement Algorithm for Undirected Trees
• Optimal Linear Ordering
• Optimal Assignments of Numbers to Vertices
• A Review of the Placement and Quadratic Assignment Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On optimal linear arrangements of trees