User menu

Strongly Polynomial Bounds for Multiobjective and Parametric Global minimum Cuts in Graphs and Hypergraphs

Bibliographic reference Aissi, Hassene ; Ridha Mahjoub, A. ; McCormick, S. Thomas ; Queyranne, Maurice. Strongly Polynomial Bounds for Multiobjective and Parametric Global minimum Cuts in Graphs and Hypergraphs. In: Mathematical Programming, Vol. 154, no.1, p. 3-28 (2015)
Permanent URL
  1. Aissi Hassene, Mahjoub A. Ridha, McCormick S. Thomas, Queyranne Maurice, A Strongly Polynomial Time Algorithm for Multicriteria Global Minimum Cuts, Integer Programming and Combinatorial Optimization (2014) ISBN:9783319075563 p.25-36, 10.1007/978-3-319-07557-0_3
  2. Armon Amitai, Zwick Uri, Multicriteria Global Minimum Cuts, 10.1007/s00453-006-0068-x
  3. Carstensen Patricia J., Complexity of some parametric integer and network programming problems, 10.1007/bf02591893
  4. Chan T. M., Output-sensitive results on convex hulls, extreme points, and related problems, 10.1007/bf02712874
  5. Chekuri, C., Korula, N.: Personal Communication (2010). Cited in: T. Fukunaga. Computing minimum multiway cuts in hypergraphs from hypertree packings. In: Integer Programming and Combinatorial Optimization (IPCO 2010), Springer LNCS 6080, pp. 15–28 (2010)
  6. Dinitz, E.A., Karzanov, A.V., Lomonosov, M.V.: On the structure of the system of minimum edge cuts in a graph. In: Fridman, A.A. (ed.) Issledovaniya po Diskretnoi Optimizatsii (Studies in Discrete Optimization), pp. 290–306. Nauka Publishers, Moscow (1976)
  7. Downey R. G., Fellows M. R., Parameterized Complexity, ISBN:9781461267980, 10.1007/978-1-4612-0515-9
  8. Ehrgott, M.: Multicriteria Optimization. Springer, Berlin (2005)
  9. Eisner Mark J., Severance Dennis G., Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases, 10.1145/321978.321982
  10. Fernández-Baca, D., Venkatachalam, B.: Sensitivity analysis in combinatorial optimization, chapter 30. In: Gonzalez, T. (ed.) Handbook of Approximation Algorithms and Metaheuristics. Chapman and Hall/CRC Press, Boca Raton (2007)
  11. Fernández-Baca David, Seppäläinen Timo, Slutzki Giora, Parametric multiple sequence alignment and phylogeny construction, 10.1016/s1570-8667(03)00078-9
  12. Hamacher H. W., Queyranne M., K best solutions to combinatorial optimization problems, 10.1007/bf02022039
  13. Hamacher H.W., Picard J.-C., Queyranne M., Ranking the Cuts and Cut-Sets of a Network, Algebraic and Combinatorial Methods in Operations Research, Proceedings of the Workshop on Algebraic Structures in Operations Research (1984) ISBN:9780444875716 p.183-200, 10.1016/s0304-0208(08)72962-1
  14. Henzinger Monika, Williamson David P., On the number of small cuts in a graph, 10.1016/0020-0190(96)00079-8
  15. Ihler Edmund, Wagner Dorothea, Wagner Frank, Modeling hypergraphs by graphs with the same mincut properties, 10.1016/0020-0190(93)90115-p
  16. Karger, D.R.: Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. In: Proceedings on Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 21–30 (1993)
  17. Karger David R., Minimum cuts in near-linear time, 10.1145/331605.331608
  18. Karger David R., Panigrahi Debmalya, A Near-Linear Time Algorithm for Constructing a Cactus Representation of Minimum Cuts, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (2009) ISBN:9780898716801 p.246-255, 10.1137/1.9781611973068.28
  19. Karger David R., Stein Clifford, A new approach to the minimum cut problem, 10.1145/234533.234534
  20. Klimmek, R., Wagner, F.: A simple hypergraph min cut algorithm. Technical Report b 96-02, Inst. of Computer Science, Freie Universität Berlin (1996)
  21. Kogan, D., Krauthgamer, R.: Sketching cuts in graphs and hypergraphs. arXiv preprint arXiv:1409.2391 (2014)
  22. Lawler Eugene L., A Procedure for Computing theKBest Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem, 10.1287/mnsc.18.7.401
  23. Lawler E. L., Cutsets and partitions of hypergraphs, 10.1002/net.3230030306
  24. Loff Barreto, B.S.: A medley for computational complexity: with applications of information theory, learning theory, and ketan mulmuley’s parametric complexity technique. PhD thesis, University of Amsterdam (2014)
  25. Mak Wai-Kei, Wong D.F., A fast hypergraph min-cut algorithm for circuit partitioning, 10.1016/s0167-9260(00)00008-0
  26. Mulmuley, K.: Computational Geometry: An Introduction Through Randomized Algorithms. Prentice-Hall, Upper Saddle River (1994)
  27. Mulmuley Ketan, Parallel vs. parametric complexity, Lecture Notes in Computer Science (1997) ISBN:9783540633075 p.282-283, 10.1007/3-540-63307-3_67
  28. Mulmuley Ketan, Lower Bounds in a Parallel Model without Bit Operations, 10.1137/s0097539794282930
  29. Murty Katta G., Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost, 10.1287/opre.16.3.682
  30. Nagamochi Hiroshi, Ibaraki Toshihide, Computing Edge-Connectivity in Multigraphs and Capacitated Graphs, 10.1137/0405004
  31. Nagamochi Hiroshi, Ibaraki Toshihide, Algorithmic Aspects of Graph Connectivity, ISBN:9780511721649, 10.1017/cbo9780511721649
  32. Nagamochi, H., Nakamura, S., Ishii, T.: Constructing a cactus for minimum cuts of a graph in $$O(mn+n^2 \log n)$$ O ( m n + n 2 log n ) space. IEICE Trans. Inf. Syst. E86-D, 179–185 (2003)
  33. Nagamochi Hiroshi, Nishimura Kazuhiro, Ibaraki Toshihide, Computing All Small Cuts in an Undirected Network, 10.1137/s0895480194271323
  34. Papadimitriou C.H., Yannakakis M., On the approximability of trade-offs and optimal access of Web sources, 10.1109/sfcs.2000.892068
  35. Panigrahi, D.: Optimization problems in network connectivity. Ph.D. thesis, MIT (2012)
  36. Preparata Franco P., Shamos Michael Ian, Computational Geometry, ISBN:9781461270102, 10.1007/978-1-4612-1098-6
  37. Queyranne, M.: Minimizing symmetric submodular functions. Math. Program. 82(1–2), 3–12 (1998)
  38. Queyranne, M., Guiñez, F.: On optimum k-way partitions with submodular costs and minimum part-size constraints. In: Talk given at the Workshop on Modern Aspects of Submodularity, Georgia Institute of Technology, Atlanta (GA) USA, March 21 (2012)
  39. Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Hoboken (1998)
  40. Seidel Raimund, The upper bound theorem for polytopes: an easy proof of its asymptotic version, 10.1016/0925-7721(95)00013-y
  41. Steiner J., Einige Gesetze über die Theilung der Ebene und des Raumes., 10.1515/crll.1826.1.349
  42. Stoer Mechthild, Wagner Frank, A simple min-cut algorithm, 10.1145/263867.263872
  43. Vazirani Vijay V., Yannakakis Mihalis, Suboptimal cuts: Their enumeration, weight and number, Automata, Languages and Programming (1992) ISBN:9783540557197 p.366-377, 10.1007/3-540-55719-9_88
  44. Hannah Honghua Yang, Wong D.F., Balanced partitioning, 10.1109/43.552086
  45. Zimmerman Seth, Slicing Space, 10.2307/2687119