Sökning: id:"swepub:oai:lup.lub.lu.se:b01033cf-bb81-4d6f-9572-78debb66907f" >
Shortest two disjoi...
Shortest two disjoint paths in polynomial time
-
- Björklund, Andreas (författare)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
- Husfeldt, Thore (författare)
- IT University of Copenhagen
-
(creator_code:org_t)
- 2019
- 2019
- Engelska 13 s.
-
Ingår i: SIAM Journal on Computing. - 0097-5397. ; 48:6, s. 1698-1710
- Relaterad länk:
-
http://dx.doi.org/10...
-
visa fler...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- Given an undirected graph and two pairs of vertices (si, ti) for i ϵ{ 1, 2} we show that there is a polynomial time Monte Carlo algorithm that finds disjoint paths of smallest total length joining si and ti 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 polynomial ring Z4[X] in combination with the isolation lemma of Mulmuley, Vazirani, and Vazirani to detect a solution. To this end, we develop a fast algorithm for permanents over the ring Zt[X], where t is a power of 2, by modifying Valiant's 1979 algorithm for the permanent over Zt
Ämnesord
- NATURVETENSKAP -- Matematik -- Diskret matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Discrete Mathematics (hsv//eng)
- TEKNIK OCH TEKNOLOGIER -- Elektroteknik och elektronik -- Signalbehandling (hsv//swe)
- ENGINEERING AND TECHNOLOGY -- Electrical Engineering, Electronic Engineering, Information Engineering -- Signal Processing (hsv//eng)
Nyckelord
- Graph algorithms
- Graph theory
- Randomized algorithms
Publikations- och innehållstyp
- art (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas