Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Analysis and Optimization of Urban Energy Systems Read chapter Read first chapter

2020 | OriginalPaper | Chapter

The Bicriterion Maximum Flow Network Interdiction Problem in s-t-Planar Graphs

Authors : Luca E. Schäfer, Tobias Dietz, Marco V. Natale, Stefan Ruzika, Sven O. Krumke, Carlos M. Fonseca

Published in: Operations Research Proceedings 2019

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

A biobjective extension of the maximum flow network interdiction problem is considered: Two maximum flows from source to sink are to be computed independently from each other while an interdictor aims to reduce the value of both maximum flows simultaneously by interdicting arcs. We show that this problem is intractable and propose two procedures to solve this problem on specific graph classes.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Convex Quadratic Mixed-Integer Problems with Quadratic Constraints
next chapter Assessment of Energy and Emission Reduction Measures in Container Terminals using PROMETHEE for Portfolio Selection
Literature
1.
Ahuja, R., Magnanti, T., Orlin, J.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Upper Saddle River (1993)
2.
Assimakopoulos, N. (1987). A network interdiction model for hospital infection control. Comput. Biol. Med. 17(6), 413–422CrossRef
3.
Boykov, Y., Kolmogorov, V.: An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Trans. Pattern Anal. Mach. Intell. 26(9), 1124–1137 (2004)CrossRef
4.
Burch, C., Carr, R., Krumke, S., Marathe, M., Phillips, C., Sundberg, E.: A decomposition-based pseudoapproximation algorithm for network flow inhibition. In: Network Interdiction and Stochastic Integer Programming, pp. 51–68. Springer, Berlin (2003)
5.
Carstensen, P.J.: Complexity of some parametric integer and network programming problems. Math. Program. 26(1), 64–75 (1983)CrossRef
6.
Chestnut, S.R., Zenklusen, R.: Hardness and approximation for network flow interdiction. Networks 69(4), 378–387 (2017)CrossRef
7.
Ehrgott, M.: Multicriteria Optimization, 2nd edn. Springer, Berlin (2005)
8.
Eppstein, D.: Parallel recognition of series-parallel graphs. Inf. Comput. 98(1), 41–55 (1992)CrossRef
9.
Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Can. J. Math. 8(3), 399–404 (1956)
10.
Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 29. wh freeman, New York (2002)
11.
Papadimitriou, C.H., Yannakakis, M.: On the approximability of trade-offs and optimal access of web sources. In: Proceedings 41st Annual Symposium on Foundations of Computer Science, pp. 86–92. IEEE, New York (2000)
12.
Phillips, C.A.: The network inhibition problem. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, pp. 776–785. ACM, New York (1993)
13.
Safer, H.M., et al.: Fast approximation schemes for multi-criteria flow, knapsack, and scheduling problems. Technical report, Massachusetts Institute of Technology (MIT), New York. Sloan School of Management
14.
Valdes, J., Tarjan, R.E., Lawler, E.L.: The recognition of series parallel digraphs. SIAM J. Comput. 11(2), 298–313 (1982)
15.
Wood, R.K.: Deterministic network interdiction. Math. Comput. Model. 17(2), 1–18 (1993)
Metadata
Title
The Bicriterion Maximum Flow Network Interdiction Problem in s-t-Planar Graphs
Authors
Luca E. Schäfer
Tobias Dietz
Marco V. Natale
Stefan Ruzika
Sven O. Krumke
Carlos M. Fonseca
Copyright Year
2020
Book
Operations Research Proceedings 2019

Print ISBN: 978-3-030-48438-5

Electronic ISBN: 978-3-030-48439-2

Copyright Year: 2020

DOI
https://doi.org/10.1007/978-3-030-48439-2_16

Premium Partner

    Image Credits