, } of clusters of terminals, all lying on the outer face of G. Output: An optimal multi-cluster cut for the input graph
On the complexity of the multicut problem in bounded treewidth graphs and digraphs, Discrete Applied Mathematics, vol.156, pp.1908-1917, 2008. ,
URL : https://hal.archives-ouvertes.fr/hal-01126374
A simple algorithm for multicuts in planar graphs with outer terminals, Discrete Applied Mathematics, vol.157, pp.1959-1964, 2009. ,
URL : https://hal.archives-ouvertes.fr/hal-01126379
A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs, Proceedings IPEC, pp.109-119, 2012. ,
URL : https://hal.archives-ouvertes.fr/hal-01126381
, Multicut is FPT. Proceedings STOC, pp.459-468, 2011.
URL : https://hal.archives-ouvertes.fr/lirmm-00741933
Efficient algorithms for k-terminal cuts on planar graphs, Algorithmica, vol.38, pp.299-316, 2004. ,
Multicuts in Planar and Bounded-Genus Graphs with Bounded Number of Terminals, Algorithmica, vol.78, pp.1206-1224, 2017. ,
Tightening Nonsimple Paths and Cycles on Surfaces, SIAM Journal on Computing, vol.39, pp.3784-3813, 2010. ,
The complexity of multiterminal cuts, SIAM Journal on Computing, vol.23, pp.864-894, 1994. ,
, Parameterized Complexity, 1999.
Primal-dual approximation algorithms for integral flow and multicut in trees, Algorithmica, vol.18, pp.3-20, 1997. ,
Approximating the k-multicut problem, Proceedings SODA, pp.621-630, 2006. ,
A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals, Proceedings ICALP, pp.677-688, 2012. ,
Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset, SIAM Journal on Computing, vol.43, pp.355-388, 2014. ,
Cutting and partitioning a graph after a fixed pattern, Proceedings ICALP, vol.154, pp.712-722, 1983. ,