2014 | OriginalPaper | Buchkapitel
Shortest Two Disjoint Paths in Polynomial Time
verfasst von : Andreas Björklund, Thore Husfeldt
Erschienen in: Automata, Languages, and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Given an undirected graph and two pairs of vertices (
s
i
,
t
i
) for
i
∈ {1,2} we show that there is a polynomial time Monte Carlo algorithm that finds disjoint paths of smallest total length joining
s
i
and
t
i
for
i
∈ {1,2} respectively, or concludes that there most likely are no such paths at all. Our algorithm applies to both the vertex- and edge-disjoint versions of the problem.
Our algorithm is algebraic and uses permanents over the quotient ring
Z
4
[
X
]/(
X
m
) in combination with Mulmuley, Vazirani and Vazirani’s isolation lemma to detect a solution. We develop a fast algorithm for permanents over said ring by modifying Valiant’s 1979 algorithm for the permanent over
$\mathbf{Z}_{2^l}$
.