Min Cut is NP-complete for edge weighted trees

DOI10.1016/0304-3975(88)90028-XzbMath0657.68034WikidataQ29030082 ScholiaQ29030082MaRDI QIDQ1111019

Ivan Hal Sudborough, Burkhard Monien

Publication date: 1988

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

weighted treessearch numberNP- completenessMin Cut linear arrangement

Mathematics Subject Classification ID

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

Related Items

Efficient reassembling of graphs. I: The linear case, On Cutwidth Parameterized by Vertex Cover, Improved self-reduction algorithms for graphs with bounded treewidth, DECONTAMINATING CHORDAL RINGS AND TORI USING MOBILE AGENTS, Computing directed pathwidth in \(O(1.89^n)\) time, Directed Pathwidth and Palletizers, Variable neighborhood search for the vertex separation problem, Pathwidth is NP-Hard for Weighted Trees, Treewidth for graphs with small chordality, Computing the vertex separation of unicyclic graphs, A branch-and-bound algorithm for the minimum cut linear arrangement problem, Visibility-based pursuit-evasion in a polygonal environment, Characterizations and directed path-width of sequence digraphs, Scheduling series-parallel task graphs to minimize peak memory, Approximating Pathwidth for Graphs of Small Treewidth, On the complexity of the storyplan problem, Pathlength of outerplanar graphs, On the complexity of the storyplan problem, Dominoes, The theory of guaranteed search on graphs, How to compute digraph width measures on directed co-graphs, Representations of graphs and networks (coding, layouts and embeddings), On cutwidth parameterized by vertex cover, Node-searching problem on block graphs, Lower bounds on the pathwidth of some grid-like graphs, Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications, Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem, Exclusive graph searching vs. pathwidth, Fixed-parameter algorithms for protein similarity search under mRNA structure constraints, Derivation of algorithms for cutwidth and related graph layout parameters, On the domination search number, Edge and node searching problems on trees, On the hardness of palletizing bins using FIFO queues, Packing of (0, 1)-matrices, On sparsification for computing treewidth, On the pathwidth of chordal graphs, Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth, On the complexity of the FIFO stack-up problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A comparison of two variations of a pebble game on graphs
• Black-white pebbles and graph separation
• The NP-completeness of the bandwidth minimization problem
• Storage requirements for deterministic polynomial time recognizable languages
• The vertex separation and search number of a graph
• Searching and pebbling
• Bandwidth and pebbling
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• On the Cutwidth and the Topological Bandwidth of a Tree
• Topological Bandwidth
• Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
• A tight bound for black and white pebbles on the pyramid
• A polynomial algorithm for the min-cut linear arrangement of trees
• A Separator Theorem for Planar Graphs
• The Pebbling Problem is Complete in Polynomial Space
• Complete Register Allocation Problems
• On Time Versus Space
• Complexity Results for Bandwidth Minimization
• Recontamination does not help to search a graph