A polynomial algorithm for the min-cut linear arrangement of trees
From MaRDI portal
Publication:3771641
DOI10.1145/4221.4228zbMath0633.68063OpenAlexW1980008391MaRDI QIDQ3771641
Publication date: 1985
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/4221.4228
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) 2-person games (91A05) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Call routing and the ratcatcher, Minimal congestion trees, Decomposability of a class of \(k\)-cutwidth critical graphs, On Cutwidth Parameterized by Vertex Cover, Pathwidth of outerplanar graphs, Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs, Bounds on the convex label number of trees, Branch and bound for the cutwidth minimization problem, Min Cut is NP-complete for edge weighted trees, Reversible Pebble Game on Trees, Polynomial-time self-reducibility: theoretical motivations and practical results∗, Pebbling meets coloring: reversible pebble game on trees, Characterizations of \(k\)-cutwidth critical trees, A branch-and-bound algorithm for the minimum cut linear arrangement problem, Parallel algorithms for the minimum cut and the minimum length tree layout problems, Cutwidth of triangular grids, Scheduling series-parallel task graphs to minimize peak memory, Strong SDP based bounds on the cutwidth of a graph, Optimal cutwidths and bisection widths of 2- and 3-dimensional meshes, An Application of Generalized Tree Pebbling to Sparse Matrix Factorization, Linear arrangement problems on recursively partitioned graphs, On the dynamics of the glass transition on Bethe lattices, Routing with critical paths, A variation on the min cut linear arrangement problem, The theory of guaranteed search on graphs, On 3-cutwidth critical graphs, Cutwidth: obstructions and algorithmic aspects, The cutwidth of trees with diameters at most 4, The structure of graphs not admitting a fixed immersion, On cutwidth parameterized by vertex cover, 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, Principal component analysis for evaluating the feasibility of cellular manufacturing without initial machine-part matrix clustering, On the complexity of tree embedding problems, A degree sequence method for the cutwidth problem of graphs, A polynomial algorithm for recognizing bounded cutwidth in hypergraphs, Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time, Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem, Bounds on mincut for Cayley graphs over Abelian groups, Tree-width, path-width, and cutwidth, On minimizing width in linear layouts, Edge and node searching problems on trees, Decompositions of critical trees with cutwidth \(k\)
