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, 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, 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, Topological Bandwidth, Embedding Outerplanar Graphs in Small Books
Cites Work
