Zobrazeno 1 - 10
of 10
pro vyhledávání: '"Bernd Zey"'
Publikováno v:
Mathematical Programming. 186:373-407
The Steiner forest problem asks for a minimum weight forest that spans a given number of terminal sets. We propose new cut- and flow-based integer linear programming formulations for the problem which yield stronger linear programming bounds than the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5145a2dd38397012ac9a0225b7c9ffd4
https://doi.org/10.1007/s10107-019-01460-6
https://doi.org/10.1007/s10107-019-01460-6
Publikováno v:
Mathematical Programming. 188:409-410
A correction to this paper has been published: https://doi.org/10.1007/s10107-021-01648-9
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::aaeaafcc5b06775c9b5586abe7167a4f
https://doi.org/10.1007/s10107-021-01648-9
https://doi.org/10.1007/s10107-021-01648-9
Publikováno v:
European Journal of Operational Research. 256:333-348
We study survivable network design problems with edge-connectivity requirements under a two-stage stochastic model with recourse and finitely many scenarios. For the formulation in the natural space of edge variables we show that facet defining inequ
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::911afb8c356720493cc0e697d467ea1f
https://doi.org/10.1016/j.ejor.2016.06.048
https://doi.org/10.1016/j.ejor.2016.06.048
Publikováno v:
Electronic Notes in Discrete Mathematics. 41:245-252
In this paper we introduce survivable network design problems under a two-stage stochastic model with fixed recourse and finitely many scenarios. We propose a new cut-based formulation based on orientation properties which is stronger than the undire
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::bd5e2d695feff0348a6275fe5508b2e1
https://doi.org/10.1016/j.endm.2013.05.099
https://doi.org/10.1016/j.endm.2013.05.099
Publikováno v:
Journal of Discrete Algorithms. 16:67-78
We propose a new algorithm that solves the Steiner tree problem on graphs with vertex set V to optimality in O(B"t"w"+"2^[email protected][email protected]?|V|) time, where tw is the [email protected]?s treewidth and the Bell numberB"k is the number
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d5c3f2702f4b80986e52700ea7febca0
Publikováno v:
Mathematical and Engineering Methods in Computer Science ISBN: 9783642360442
MEMICS
MEMICS
We consider the Steiner tree problem in graphs under uncertainty, the so-called two-stage stochastic Steiner tree problem (SSTP). The problem consists of two stages: In the first stage, we do not know which nodes need to be connected. Instead, we kno
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::db835396d211cb0d499ced3c26275485
https://doi.org/10.1007/978-3-642-36046-6_14
https://doi.org/10.1007/978-3-642-36046-6_14
Publikováno v:
Algorithms and Computation ISBN: 9783642175169
ISAAC (1)
ISAAC (1)
We consider the Steiner tree problem under a two-stage stochastic model with recourse and finitely many scenarios. In this prob- lem, edges are purchased in the first stage when only probabilistic infor- mation on the set of terminals and the future
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2a88017b2831ec23dc6346cdcb3f8aac
https://kups.ub.uni-koeln.de/54996/
https://kups.ub.uni-koeln.de/54996/
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783642250101
IWOCA
IWOCA
We propose a new algorithm that solves the Steiner tree problem on graphs with vertex set V to optimality in $\ensuremath{\mathcal{O}(B_{\ensuremath{\textit{tw}}+2}^2 \cdot \ensuremath{\textit{tw}}\ \cdot |V|)}$ time, where $\ensuremath{\textit{tw}}$
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ed47ac29cb76bab26f3ad9bc7c2470f3
https://doi.org/10.1007/978-3-642-25011-8_30
https://doi.org/10.1007/978-3-642-25011-8_30
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783642028816
COCOON
COCOON
Given a planar graph G = (V ,E ), the planar biconnectivity augmentation problem (PBA) asks for an edge set E *** *** V ×V such that G + E *** is planar and biconnected. This problem is known to be $\mathcal{NP}$-hard in general; see [1]. We show th
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b1fcfdfd39e9849d9311fd768a381277
https://doi.org/10.1007/978-3-642-02882-3_25
https://doi.org/10.1007/978-3-642-02882-3_25
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783642102165
IWOCA
IWOCA
A combinatorial embedding ${\it \Pi}$ of a planar graph G = (V,E) is defined by the cyclic order of incident edges around each vertex in a planar drawing of G. The planar biconnectivity augmentation problem with fixed embedding (PBA-Fix) asks for a m
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::74499967352cb2b517666ac63c64154a
https://doi.org/10.1007/978-3-642-10217-2_29
https://doi.org/10.1007/978-3-642-10217-2_29