Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees
From MaRDI portal
Publication:3951561
DOI10.1137/0603010zbMath0489.68060MaRDI QIDQ3951561
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
polynomial time algorithm; VSLI design; m-ary trees; one-dimensional layout problems for undirected graphs
68R10: Graph theory (including graph drawing) in computer science
94C15: Applications of graph theory to circuits and networks
Related Items
Cutwidth of the de Bruijn graph, Graph layout problems, On minimizing width in linear layouts, On optimal linear arrangements of 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, Bounds on the convex label number of trees, On embedding graphs in trees, Graphs with small bandwidth and cutwidth, The cyclic cutwidth of trees, Maximum cutwidth problem for graphs., The cutwidth of trees with diameters at most 4, Tree-width, path-width, and cutwidth, Linear graph grammars: Power and complexity, Vertex ordering and partitioning problems for random spatial graphs., HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting, Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem, On the thinness and proper thinness of a graph, On the dynamics of the glass transition on Bethe lattices, On the relationship between NLC-width and linear NLC-width, Cutwidth of ther-dimensional Mesh ofd-ary Trees, 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, Topological Bandwidth, Embedding Outerplanar Graphs in Small Books
Cites Work