EUVIMEDEUVIMED entdecken
Crossref

Protecting the Connectivity of a Graph Under Nonuniform Edge Failures

Felix Hommelsheim, Zhenwei Liu, Nicole Megow, Guochuan Zhang

SIAM Journal on Discrete Mathematics · 30.09.2026 · 40 (3) · 1141-1167

DOI: 10.1137/25m1767819 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 23.07.2026. Verfasst von Felix Hommelsheim und 3 weiteren Autor:innen. Die Arbeit nennt 52 Literaturangaben. Gefördert von: National Natural Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study the problem of guaranteeing the connectivity of a given graph by protecting or strengthening edges. Herein, a protected edge is assumed to be robust and will not fail, which features a nonuniform failure model. We introduce the [Formula: see text]-Steiner-Connectivity Preservation problem where we protect a minimum-cost set of edges such that the underlying graph maintains [Formula: see text]-edge-connectivity between given terminal pairs against edge failures, assuming at most [Formula: see text] unprotected edges can fail. We design polynomial-time exact algorithms for the cases where [Formula: see text] and [Formula: see text] are small and approximation algorithms for general values of [Formula: see text] and [Formula: see text]. Additionally, we show that when both [Formula: see text] and [Formula: see text] are part of the input, even deciding whether a given solution is feasible is [Formula: see text]-complete. This hardness also carries over to Flexible Network Design, a research direction that has gained significant attention. In particular, previous work focuses on problem settings where either [Formula: see text] or [Formula: see text] is constant, for which our new hardness result now provides justification.

Förderung

  • National Natural Science Foundation of China

Zitieren

APA

Hommelsheim, F., Liu, Z., Megow, N., & Zhang, G. (2026). Protecting the Connectivity of a Graph Under Nonuniform Edge Failures. SIAM Journal on Discrete Mathematics, 40(3), 1141-1167. https://doi.org/10.1137/25m1767819

Vancouver

Hommelsheim F, Liu Z, Megow N, Zhang G. Protecting the Connectivity of a Graph Under Nonuniform Edge Failures. SIAM Journal on Discrete Mathematics. 2026;40(3):1141-1167. doi:10.1137/25m1767819

BibTeX
@article{Hommelsheim2026,
  author = {Hommelsheim, Felix and Liu, Zhenwei and Megow, Nicole and Zhang, Guochuan},
  title = {Protecting the Connectivity of a Graph Under Nonuniform Edge Failures},
  journal = {SIAM Journal on Discrete Mathematics},
  year = {2026},
  volume = {40},
  number = {3},
  pages = {1141--1167},
  doi = {10.1137/25m1767819}
}
Kostenlos starten →