New results on planar and directed multicuts

Electronic Notes in Discrete Mathematics - Tập 34 - Trang 207-211 - 2009
Cédric Bentz1
1LRI, Univ. Paris-Sud and CNRS 91405 Orsay, France

Tài liệu tham khảo

Bentz, 2009, A simple algorithm for multicuts in planar graphs with outer terminals, Discrete Applied Mathematics, 157, 1959, 10.1016/j.dam.2008.11.010

Bentz, 2008, On the complexity of the multicut problem in bounded tree-width graphs and digraphs, Discrete Applied Mathematics, 156, 1908, 10.1016/j.dam.2007.09.013

Chawla, S., R. Krauthgamer, R. Kumar, Y. Rabani and D. Sivakumar, On the hardness of approximating multicut and sparsest-cut, Proc. CCC (2005)

Chen, 2004, Efficient algorithms for k-terminal cuts on planar graphs, Algorithmica, 38, 299, 10.1007/s00453-003-1061-2

Chuzhoy, J., and S. Khanna, Hardness of cut problems in directed graphs, Proc. STOC (2006), 527–536

Colin de Verdière, E., and J. Erickson, Tightening non-simple paths and cycles on surfaces, Proc. SODA (2006), 192–201

Costa, 2005, Minimal multicut and maximal integer multiflow: a survey, European J. of Operational Research, 162, 55, 10.1016/j.ejor.2003.10.037

Dahlhaus, 1994, The complexity of multiterminal cuts, SIAM J. Comput., 23, 864, 10.1137/S0097539792225297

Downey, 1999

Garg, 1997, Primal-dual approximation algorithms for integral flow and multicut in trees, Algorithmica, 18, 3, 10.1007/BF02523685

Garg, 2004, Multiway cuts in node weighted graphs, Journal of Algorithms, 50, 49, 10.1016/S0196-6774(03)00111-1

Yeh, 2001, A simple algorithm for the planar multiway cut problem, Journal of Algorithms, 39, 68, 10.1006/jagm.2000.1148

Thông tin
Thông tin xuất bản

Electronic Notes in Discrete Mathematics

Tập 34

207-211

Thông tin tác giả