EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Shortest Two Disjoint Paths in Conservative Graphs

Ildikó Schlotter

Algorithmica · 2026-04 · 88 (2)

DOI: 10.1007/s00453-026-01375-7 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Algorithmica, online erschienen am 21.03.2026. Verfasst von Ildikó Schlotter. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 17 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Magyar Tudományos Akadémia.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We consider the following problem that we call the Shortest Two Disjoint Paths problem: given an undirected graph $$G=(V,E)$$ G = ( V , E ) with edge weight function $${w:E\rightarrow \mathbb {R}}$$ w : E → R , two terminals s and t in G , find two internally vertex-disjoint paths between s and t with minimum total weight. As shown recently by Schlotter and Sebő (2022), this problem becomes $$\textsf{NP}$$ NP -hard if edges can have negative weights, even if the weight function is conservative, i.e., there are no cycles in G with negative total weight. We propose a polynomial-time algorithm that solves the Shortest Two Disjoint Paths problem for conservative weights in the case when the negative-weight edges form a constant number of trees in G .

Förderung

  • Magyar Tudományos Akadémia

Zitieren

APA

Schlotter, I. (2026). Shortest Two Disjoint Paths in Conservative Graphs. Algorithmica, 88(2). https://doi.org/10.1007/s00453-026-01375-7

Vancouver

Schlotter I. Shortest Two Disjoint Paths in Conservative Graphs. Algorithmica. 2026;88(2). doi:10.1007/s00453-026-01375-7

BibTeX
@article{Schlotter2026,
  author = {Schlotter, Ildikó},
  title = {Shortest Two Disjoint Paths in Conservative Graphs},
  journal = {Algorithmica},
  year = {2026},
  volume = {88},
  number = {2},
  doi = {10.1007/s00453-026-01375-7}
}
Kostenlos starten →