Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
From MaRDI portal
Publication:3740255
DOI10.1137/0214013zbMath0603.68068OpenAlexW2143314829MaRDI QIDQ3740255
Fillia Makedon, Moon Jung Chung, Ivan Hal Sudborough, Jonathan S. Turner
Publication date: 1985
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0214013
VLSIcutwidthforbidden subgraph characterizationsearch numberintegrated circuit layoutfolding numberblack/white pebble demanddegree three treeslayout of Weinberger arraysMin Cut Linear Arrangement
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Decomposability of a class of \(k\)-cutwidth critical graphs, On Cutwidth Parameterized by Vertex Cover, On the Cooperative Graph Searching Problem, Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs, Bounds on the convex label number of trees, Min Cut is NP-complete for edge weighted trees, Characterizations of \(k\)-cutwidth critical trees, Graph layout problems, Efficient parallel algorithms for some tree layout problems, The cutwidth of trees with diameters at most 4, On cutwidth parameterized by vertex cover, On the k-ary hypercube, Neighbourhood-width of trees, Embedding grids into hypercubes, Search and sweep numbers of finite directed acyclic graphs, A degree sequence method for the cutwidth problem of graphs, A polynomial algorithm for recognizing bounded cutwidth in hypergraphs, Minimal trees of given search number, Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time, 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, Edge and node searching problems on trees, Decompositions of critical trees with cutwidth \(k\), On the Cutwidth and the Topological Bandwidth of a Tree, Topological Bandwidth
