Min Cut is NP-complete for edge weighted trees
From MaRDI portal
Publication:1111019
DOI10.1016/0304-3975(88)90028-XzbMATH Open0657.68034DBLPjournals/tcs/MonienS88WikidataQ29030082 ScholiaQ29030082MaRDI QIDQ1111019FDOQ1111019
I. H. Sudborough, Burkhard Monien
Publication date: 1988
Published in: Theoretical Computer Science (Search for Journal in Brave)
Recommendations
- scientific article; zbMATH DE number 3956440
- An improved algorithm for the planar 3-cut problem
- scientific article; zbMATH DE number 3858434
- A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs
- A fast algorithm for minimum weight odd circuits and cuts in planar graphs
- A note on finding minimum cuts in directed planar networks by parallel computations
- An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem
- Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
- scientific article
- The Complexity of Multiterminal Cuts
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Title not available (Why is that?)
- Searching and pebbling
- A Separator Theorem for Planar Graphs
- Title not available (Why is that?)
- Recontamination does not help to search a graph
- The NP-completeness of the bandwidth minimization problem
- The vertex separation and search number of a graph
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- Complexity Results for Bandwidth Minimization
- Topological Bandwidth
- A polynomial algorithm for the min-cut linear arrangement of trees
- Black-white pebbles and graph separation
- Title not available (Why is that?)
- On Time Versus Space
- Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
- Complete Register Allocation Problems
- Title not available (Why is that?)
- On the Cutwidth and the Topological Bandwidth of a Tree
- Storage requirements for deterministic polynomial time recognizable languages
- Bandwidth and pebbling
- The Pebbling Problem is Complete in Polynomial Space
- A comparison of two variations of a pebble game on graphs
- A tight bound for black and white pebbles on the pyramid
Cited In (41)
- Approximating Pathwidth for Graphs of Small Treewidth
- On the complexity of the FIFO stack-up problem
- On the hardness of palletizing bins using FIFO queues
- On sparsification for computing treewidth
- Dominoes
- On Cutwidth Parameterized by Vertex Cover
- Title not available (Why is that?)
- Directed Pathwidth and Palletizers
- Treewidth for graphs with small chordality
- Computing directed pathwidth in \(O(1.89^n)\) time
- Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth
- Characterizations and directed path-width of sequence digraphs
- On the domination search number
- Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem
- Visibility-based pursuit-evasion in a polygonal environment
- Edge and node searching problems on trees
- On the pathwidth of chordal graphs
- On the complexity of the storyplan problem
- On the complexity of the storyplan problem
- Variable neighborhood search for the vertex separation problem
- Lower bounds on the pathwidth of some grid-like graphs
- Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
- Computing the vertex separation of unicyclic graphs
- The theory of guaranteed search on graphs
- DECONTAMINATING CHORDAL RINGS AND TORI USING MOBILE AGENTS
- Node-searching problem on block graphs
- Improved self-reduction algorithms for graphs with bounded treewidth
- Derivation of algorithms for cutwidth and related graph layout parameters
- On cutwidth parameterized by vertex cover
- How to compute digraph width measures on directed co-graphs
- Efficient reassembling of graphs. I: The linear case
- Fixed-parameter algorithms for protein similarity search under mRNA structure constraints
- Scheduling series-parallel task graphs to minimize peak memory
- A branch-and-bound algorithm for the minimum cut linear arrangement problem
- A note on the minimum cut cover of graphs
- Packing of (0, 1)-matrices
- Graph searching on chordal graphs
- Pathwidth is NP-Hard for Weighted Trees
- Exclusive graph searching vs. pathwidth
- Pathlength of outerplanar graphs
- Representations of graphs and networks (coding, layouts and embeddings)
This page was built for publication: Min Cut is NP-complete for edge weighted trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1111019)
