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

DOI10.1137/0214013zbMATH Open0603.68068OpenAlexW2143314829MaRDI QIDQ3740255FDOQ3740255

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

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

VLSI cutwidth forbidden subgraph characterization search number integrated circuit layout folding number black/white pebble demand degree three trees layout of Weinberger arrays Min 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)

Cited In (35)

Optimal cuts and partitions in tree metrics in polynomial time
Characterizations of \(k\)-cutwidth critical trees
A polynomial algorithm for recognizing bounded cutwidth in hypergraphs
A degree sequence method for the cutwidth problem of graphs
Title not available (Why is that?)
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
Title not available (Why is that?)
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
Efficient parallel algorithms for some tree layout problems
Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition
Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs
Graph layout problems
Cutwidth II: Algorithms for partial w-trees of bounded degree
Embedding grids into hypercubes
On the k-ary hypercube
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
On the Cooperative Graph Searching Problem
Neighbourhood-width of trees
Title not available (Why is that?)
Search and sweep numbers of finite directed acyclic graphs
Title not available (Why is that?)
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)