Shortest two disjoint paths in conservative graphs

July 24, 2023 Β· Declared Dead Β· πŸ› Symposium on Theoretical Aspects of Computer Science

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors IldikΓ³ Schlotter arXiv ID 2307.12602 Category cs.DS: Data Structures & Algorithms Citations 1 Venue Symposium on Theoretical Aspects of Computer Science Last Checked 4 months ago
Abstract
We consider the following problem that we call the Shortest Two Disjoint Paths problem: given an undirected graph $G=(V,E)$ with edge weights $w:E \rightarrow \mathbb{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 NP-hard if edges can have negative weights, even if the weight function is conservative, 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$.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted