Blocking unions of arborescences

Discrete Optimization - Tập 22 - Trang 277-290 - 2016
Attila Bernáth1, Gyula Pap1
1MTA-ELTE Egerváry Research Group, Department of Operations Research, Eötvös University, Pázmány Péter sétány 1/C, Budapest, H-1117, Hungary

Tài liệu tham khảo

Schrijver, 2003 Frank, 1978, On disjoint trees and arborescences, vol.~25, 159 Bernáth, 2013, Blocking optimal arborescences, 74 Thomas McCormick, 1983 Vardy, 1997, The intractability of computing the minimum distance of a code, IEEE Trans. Inform. Theory, 43, 1757, 10.1109/18.641542 Nagamochi, 1992, Computing edge-connectivity in multigraphs and capacitated graphs, SIAM J. Discrete Math., 5, 54, 10.1137/0405004 Király, 2009 2011 Gwenaël Joret, Adrian Vetta, Reducing the rank of a matroid, 2012, arXiv preprint arXiv:1211.4853. Apollonio, 2014, The maximum vertex coverage problem on bipartite graphs, Discrete Appl. Math., 165, 37, 10.1016/j.dam.2013.05.015 Kamiyama, 2012, Robustness of minimum cost arborescences, Jpn. J. Ind. Appl. Math., 29, 485, 10.1007/s13160-012-0079-8 Bernáth, 2015 Frederickson, 1999, Increasing the weight of minimum spanning trees, J. Algorithms, 33, 244, 10.1006/jagm.1999.1026 Liang, 1997, Finding the k most vital edges in the minimum spanning tree problem, Parallel Comput., 23, 1889, 10.1016/S0167-8191(97)00098-7 Zenklusen, 2009, Blockers and transversals, Discrete Math., 309, 4306, 10.1016/j.disc.2009.01.006 Zenklusen, 2010, Matching interdiction, Discrete Appl. Math., 158, 1676, 10.1016/j.dam.2010.06.006 Dinitz, 2013, Packing interdiction and partial covering problems, 157 Edmonds, 1973, Edge-disjoint branchings, Combin. Algorithms, 9, 91 Frank, 1979, Covering branchings, Acta Sci. Math. (Szeged), 41, 3 Bárász, 2005, An algorithm for source location in directed graphs, Oper. Res. Lett., 33, 221, 10.1016/j.orl.2004.07.005 Ito, 2003, Source location problem with flow requirements in directed networks, Optim. Methods Softw., 18, 427, 10.1080/1055-6780309510593 András Frank, Some polynomial algorithms for certain graphs and hypergraphs, in: Proceedings of the Fifth British Combinatorial Conference, 1975, pp. 211–226. Orlin, 2013, Max flows in O(nm) time, or better, 765 Hao, 1994, A faster algorithm for finding the minimum cut in a directed graph, J. Algorithms, 17, 424, 10.1006/jagm.1994.1043