Parameterized complexity of multicut in weighted trees

DOI10.1016/J.TCS.2023.114174MaRDI QIDQ6050131zbMATH OpenFDO

Authors Esther Galby, Dániel Marx, Philipp Schepper, Roohani Sharma, Prafullkumar Tale

Publication date 12 October 2023

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

Full work available at URL https://doi.org/10.1016/J.TCS.2023.114174

zbMATH Keywords

directed flow augmentationmulticut in weighted treesweighted digraph pair cut

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
• Algorithmic graph theory and perfect graphs
• Algorithms for cut problems on trees
• Approximating Bandwidth by Mixing Layouts of Interval Graphs
• Cluster deletion on interval graphs and split related graphs
• Clustering with local restrictions
• Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
• Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
• Connected domination and steiner set on asteroidal triple-free graphs
• Directed subset feedback vertex set is fixed-parameter tractable
• Dominating sets for split and bipartite graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Enumerating minimal subset feedback vertex sets
• Exact algorithms and applications for tree-like Weighted Set Cover
• Finding Hamiltonian circuits in interval graphs
• Finding the minimum bandwidth of an interval graph
• Fixed-parameter tractability and data reduction for multicut in trees
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Graph theory
• scientific article; zbMATH DE number 3876616 (Why is no real title available?)
• In memoriam Walter Kern
• Multicut in trees viewed through the eyes of vertex cover
• Multicut Is FPT
• On the tractability of optimization problems on \(H\)-graphs
• Parameterized algorithms
• Parameterized graph separation problems
• Parameterized tractability of multiway cut with parity constraints
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Restricted vertex multicut on permutation graphs
• Steiner trees, connected domination and strongly chordal graphs
• Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable (extended abstract)
• The Complexity of Multiterminal Cuts
• The leafage of a chordal graph
• The longest path problem has a polynomial solution on interval graphs
• Token sliding on split graphs

Cited in

(5)

• FPTAS’s for Some Cut Problems in Weighted Trees
• scientific article; zbMATH DE number 3956440 (Why is no real title available?)
• Optimal cuts and partitions in tree metrics in polynomial time
• scientific article; zbMATH DE number 6850362 (Why is no real title available?)
• A POLYNOMIAL KERNEL FOR MULTICUT IN TREES

This page was built for publication: Parameterized complexity of multicut in weighted trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6050131)