Disser, Yann ; Matuschke, Jannik (2020)
The Complexity of Computing a Robust Flow.
In: Operations Research Letters, 48 (1)
doi: 10.1016/j.orl.2019.10.012
Artikel, Bibliographie
Kurzbeschreibung (Abstract)
The Maximum Robust Flow problem asks for a flow on the paths of a network maximizing the guaranteed amount of flow surviving the removal of any arcs. We point out a flaw in a previous publication that claimed -hardness for this problem when . For the case that is part of the input, we present a new hardness proof. We also discuss the complexity of the integral version of the problem.
| Typ des Eintrags: | Artikel |
|---|---|
| Erschienen: | 2020 |
| Autor(en): | Disser, Yann ; Matuschke, Jannik |
| Art des Eintrags: | Bibliographie |
| Titel: | The Complexity of Computing a Robust Flow |
| Sprache: | Englisch |
| Publikationsjahr: | Januar 2020 |
| Verlag: | Elsevier |
| Titel der Zeitschrift, Zeitung oder Schriftenreihe: | Operations Research Letters |
| Jahrgang/Volume einer Zeitschrift: | 48 |
| (Heft-)Nummer: | 1 |
| DOI: | 10.1016/j.orl.2019.10.012 |
| Kurzbeschreibung (Abstract): | The Maximum Robust Flow problem asks for a flow on the paths of a network maximizing the guaranteed amount of flow surviving the removal of any arcs. We point out a flaw in a previous publication that claimed -hardness for this problem when . For the case that is part of the input, we present a new hardness proof. We also discuss the complexity of the integral version of the problem. |
| Fachbereich(e)/-gebiet(e): | Exzellenzinitiative Exzellenzinitiative > Graduiertenschulen Exzellenzinitiative > Graduiertenschulen > Graduate School of Computational Engineering (CE) |
| Hinterlegungsdatum: | 15 Jul 2022 07:44 |
| Letzte Änderung: | 15 Jul 2022 07:44 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum