Min Cut is NP-complete for edge weighted trees
From MaRDI portal
(Redirected from Publication:1111019)
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; zbMATH DE number 4145687
- The Complexity of Multiterminal Cuts
Cites work
- scientific article; zbMATH DE number 3650583 (Why is no real title available?)
- scientific article; zbMATH DE number 3813518 (Why is no real title available?)
- scientific article; zbMATH DE number 3590298 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- A Separator Theorem for Planar Graphs
- A comparison of two variations of a pebble game on graphs
- A polynomial algorithm for the min-cut linear arrangement of trees
- A tight bound for black and white pebbles on the pyramid
- Bandwidth and pebbling
- Black-white pebbles and graph separation
- Complete Register Allocation Problems
- Complexity Results for Bandwidth Minimization
- On Time Versus Space
- On the Cutwidth and the Topological Bandwidth of a Tree
- Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
- Recontamination does not help to search a graph
- Searching and pebbling
- Storage requirements for deterministic polynomial time recognizable languages
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- The NP-completeness of the bandwidth minimization problem
- The Pebbling Problem is Complete in Polynomial Space
- The vertex separation and search number of a graph
- Topological Bandwidth
Cited in
(47)- Pathwidth is NP-Hard for Weighted Trees
- Pathlength of outerplanar graphs
- On the complexity of the FIFO stack-up problem
- Approximating Pathwidth for Graphs of Small Treewidth
- On the hardness of palletizing bins using FIFO queues
- \textsc{Telephone Broadcast} on graphs of treewidth two
- Dominoes
- scientific article; zbMATH DE number 3956440 (Why is no real title available?)
- Treewidth for graphs with small chordality
- Computing directed pathwidth in O(1.89ⁿ) time
- Characterizations and directed path-width of sequence digraphs
- Pathlength of outerplanar graphs
- Complexity framework for forbidden subgraphs. I: The framework
- On the domination search number
- Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem
- Edge and node searching problems on trees
- Visibility-based pursuit-evasion in a polygonal environment
- Complexity of the virtual network embedding with uniform demands
- On the pathwidth of chordal graphs
- Variable neighborhood search for the vertex separation problem
- Lower bounds on the pathwidth of some grid-like graphs
- On the complexity of the storyplan problem
- On the complexity of the storyplan problem
- Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
- On the complexity of isoperimetric problems on trees
- Computing the vertex separation of unicyclic graphs
- The theory of guaranteed search on graphs
- Node-searching problem on block graphs
- Improved self-reduction algorithms for graphs with bounded treewidth
- DECONTAMINATING CHORDAL RINGS AND TORI USING MOBILE AGENTS
- On cutwidth parameterized by vertex cover
- Derivation of algorithms for cutwidth and related graph layout parameters
- Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
- 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
- Treewidth is NP-complete on cubic graphs
- Treewidth is NP-complete on cubic graphs
- Directed pathwidth and palletizers
- Exclusive graph searching vs. pathwidth
- 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)
