Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
Authors:
- Jiong GuoJGJiong Guo
- Falk HüffnerFHFalk Hüffner
- Erhan KenarEKErhan Kenar
- Rolf NiedermeierRNRolf Niedermeier
- Johannes UhlmannJUJohannes Uhlmann
- 1 April 2008
- journal article
- Published by Elsevier in European Journal of Operational Research
- Vol. 186 (2) , 542-553
Abstract
No abstract availableThis publication has 15 references indexed in Scilit:
- Fixed‐parameter tractability and data reduction for multicut in treesNetworks, 2005
- Minimal multicut and maximal integer multiflow: A surveyEuropean Journal of Operational Research, 2005
- Multiway cuts in node weighted graphsJournal of Algorithms, 2004
- Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-widthJournal of Algorithms, 2003
- Graph Classes: A Survey1999
- A partial k-arboretum of graphs with bounded treewidthTheoretical Computer Science, 1998
- Primal-dual approximation algorithms for integral flow and multicut in treesAlgorithmica, 1997
- The Complexity of Multiterminal CutsSIAM Journal on Computing, 1994
- Evolutionary trees: An integer multicommodity max-flow-min-cut theoremAdvances in Applied Mathematics, 1992
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithmsJournal of Computer and System Sciences, 1976