A polynomial algorithm for the min-cut linear arrangement of trees

DOI10.1145/4221.4228zbMath0633.68063OpenAlexW1980008391MaRDI QIDQ3771641

Mihalis Yannakakis

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

zbMATH Keywords

cutwidthmin-cut linear arrangement

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) 2-person games (91A05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (47)

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 ⋮ Parameterized algorithms for minimum sum vertex cover ⋮ 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\)

This page was built for publication: A polynomial algorithm for the min-cut linear arrangement of trees