Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees

DOI10.1137/0603010zbMath0489.68060OpenAlexW1970580433MaRDI QIDQ3951561

Thomas Lengauer

Publication date: 1982

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0603010

zbMATH Keywords

polynomial time algorithmVSLI designm-ary treesone-dimensional layout problems for undirected graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Related Items

Vertex ordering and partitioning problems for random spatial graphs., Bounds on the convex label number of trees, On embedding graphs in trees, Graphs with small bandwidth and cutwidth, Embedding Outerplanar Graphs in Small Books, On the thinness and proper thinness of a graph, Graph layout problems, Optimal cutwidths and bisection widths of 2- and 3-dimensional meshes, On the dynamics of the glass transition on Bethe lattices, Maximum cutwidth problem for graphs., HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting, The cutwidth of trees with diameters at most 4, Cutwidth of the de Bruijn graph, Dynamics of Ising models near zero temperature: real-space renormalization approach, Dynamical barriers for the random ferromagnetic Ising model on the Cayley tree: traveling-wave solution of the real space renormalization flow, Cutwidth of ther-dimensional Mesh ofd-ary Trees, Minimal cutwidth linear arrangements of abelian Cayley graphs, Graph parameters measuring neighbourhoods in graphs-bounds and applications, Optimal cuts in graphs and statistical mechanics, Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem, Tree-width, path-width, and cutwidth, On minimizing width in linear layouts, The cyclic cutwidth of trees, Linear graph grammars: Power and complexity, On optimal linear arrangements of trees, On the relationship between NLC-width and linear NLC-width, Topological Bandwidth

Cites Work

• The space complexity of pebble games on trees
• A Minimum Linear Arrangement Algorithm for Undirected Trees
• Optimal Assignments of Numbers to Vertices
• Unnamed Item
• Unnamed Item