Shortest Two Disjoint Paths in Polynomial Time
Författare
Redaktör
- Esparza Javier
- Fraigniaud Pierre
- Husfeldt Thore
- Koutsoupias Elias
Summary, in English
Given an undirected graph and two pairs of vertices $(s_i,t_i)$ for $i\in\{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\in\{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 polynomial rings $Z_2[x]$ and $Z_4[x]$ in combination with Mulmuley, Vazirani and Vazirani's isolation lemma to detect a solution. We develop a fast algorithm for permanents over these rings by modifying Valiant's 1979 algorithm for the permanent over $Z_{2^l}$.
Our algorithm is algebraic and uses permanents over the polynomial rings $Z_2[x]$ and $Z_4[x]$ in combination with Mulmuley, Vazirani and Vazirani's isolation lemma to detect a solution. We develop a fast algorithm for permanents over these rings by modifying Valiant's 1979 algorithm for the permanent over $Z_{2^l}$.
Avdelning/ar
Publiceringsår
2014
Språk
Engelska
Sidor
211-222
Publikation/Tidskrift/Serie
Lecture Notes in Computer Science
Volym
8572
Dokumenttyp
Konferensbidrag
Förlag
Springer
Ämne
- Computer Science
Conference name
Automata, Languages, and Programming : 41st International Colloquium, ICALP 2014
Conference date
2014-07-08 - 2014-08-11
Conference place
Copenhagen, Denmark
Status
Published
Projekt
- Exact algorithms
Forskningsgrupp
- Algorithms
ISBN/ISSN/Övrigt
- ISSN: 0302-9743
- ISSN: 1611-3349
- ISBN: 978-3-662-43947-0