Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees

DOI10.1137/0214013MaRDI QIDQ3740255zbMATH OpenOpenAlexFDO

Authors Moon Jung Chung, Fillia Makedon, I. H. 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

zbMATH Keywords

VLSIcutwidthforbidden subgraph characterizationsearch numberintegrated circuit layoutfolding numberblack/white pebble demanddegree three treeslayout of Weinberger arraysMin Cut Linear Arrangement

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A polynomial algorithm for the min-cut linear arrangement of trees
• A Polynomial Algorithm for the Degree-Constrained Minimum K-Tree Problem
• scientific article; zbMATH DE number 1875430
• Polynomial time approximation schemes for the constrained minimum spanning tree problem
• Algorithms for cut problems on trees
• Polynomial time algorithm for min-ranks of graphs with simple tree structures
• On minimum bisection and related cut problems in trees and tree-like graphs
• On algorithms employing treewidth for \(L\)-bounded cut problems
• Improved parameterized and exact algorithms for cut problems on trees
• Polynomial-time approximation scheme for minimum \(k\)-cut in planar and minor-free graphs

Cited in

(35)

• Optimal cuts and partitions in tree metrics in polynomial time
• Characterizations of \(k\)-cutwidth critical trees
• A degree sequence method for the cutwidth problem of graphs
• A polynomial algorithm for recognizing bounded cutwidth in hypergraphs
• scientific article; zbMATH DE number 1875430 (Why is no real title available?)
• Bounds on the convex label number of trees
• The cutwidth of trees with diameters at most 4
• Decomposability of a class of \(k\)-cutwidth critical graphs
• Min Cut is NP-complete for edge weighted trees
• scientific article; zbMATH DE number 3956440 (Why is no real title available?)
• Decompositions of critical trees with cutwidth \(k\)
• Topological Bandwidth
• A polynomial algorithm for the min-cut linear arrangement of trees
• Minimal trees of given search number
• Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem
• Edge and node searching problems on trees
• Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition
• Efficient parallel algorithms for some tree layout problems
• Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs
• Graph layout problems
• On the k-ary hypercube
• Embedding grids into hypercubes
• Cutwidth II: Algorithms for partial w-trees of bounded degree
• On cutwidth parameterized by vertex cover
• On minimizing width in linear layouts
• On cutwidth parameterized by vertex cover
• On the Cutwidth and the Topological Bandwidth of a Tree
• Tree-width, path-width, and cutwidth
• Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
• Neighbourhood-width of trees
• On the Cooperative Graph Searching Problem
• scientific article; zbMATH DE number 177539 (Why is no real title available?)
• Search and sweep numbers of finite directed acyclic graphs
• scientific article; zbMATH DE number 3958752 (Why is no real title available?)
• Computing the cutwidth of bipartite permutation graphs in linear time

This page was built for publication: Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3740255)