Parameterized complexity of multicut in weighted trees
From MaRDI portal
Publication:6050131
DOI10.1016/j.tcs.2023.114174MaRDI QIDQ6050131
Roohani Sharma, Philipp Schepper, Dániel Marx, Prafullkumar Tale, Esther Galby
Publication date: 12 October 2023
Published in: Theoretical Computer Science (Search for Journal in Brave)
Cites Work
- Unnamed Item
- Unnamed Item
- Multicut in trees viewed through the eyes of vertex cover
- Restricted vertex multicut on permutation graphs
- Enumerating minimal subset feedback vertex sets
- List H-coloring a graph by removing few vertices
- The longest path problem has a polynomial solution on interval graphs
- Primal-dual approximation algorithms for integral flow and multicut in trees
- On the computational complexity of vertex integrity and component order connectivity
- Dominating sets for split and bipartite graphs
- Parameterized graph separation problems
- Exact algorithms and applications for tree-like Weighted Set Cover
- Finding Hamiltonian circuits in interval graphs
- Finding the minimum bandwidth of an interval graph
- Algorithmic graph theory and perfect graphs
- Clustering with local restrictions
- In memoriam Walter Kern
- Cluster deletion on interval graphs and split related graphs
- Token sliding on split graphs
- Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
- On the tractability of optimization problems on \(H\)-graphs
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
- Parameterized Tractability of Multiway Cut with Parity Constraints
- Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
- Algorithms for Cut Problems on Trees
- Hadwiger Number of Graphs with Small Chordality
- Fixed-parameter tractability and data reduction for multicut in trees
- Steiner trees, connected domination and strongly chordal graphs
- A Linear Time Algorithm for Deciding Interval Graph Isomorphism
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- The leafage of a chordal graph
- The Complexity of Multiterminal Cuts
- Directed multicut is W[1-hard, even for four terminal pairs]
- Multicut Is FPT
- Approximating Bandwidth by Mixing Layouts of Interval Graphs
- Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- Connected domination and steiner set on asteroidal triple-free graphs
- A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
- Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
- Parameterized Algorithms
- Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
- Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs
- Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable (extended abstract)
This page was built for publication: Parameterized complexity of multicut in weighted trees