Fomin, Fedor V. ; Lokshtanov, Daniel ; Saurabh, Saket (2011) An exact algorithm for minimum distortion embedding Theoretical Computer Science, 412 (29). pp. 3530-3536. ISSN 0304-3975
Full text not available from this repository.
Official URL: http://doi.org/10.1016/j.tcs.2011.02.043
Related URL: http://dx.doi.org/10.1016/j.tcs.2011.02.043
Abstract
Let G be an unweighted connected graph on n vertices. We show that an embedding of the shortest path metric of G into the line with minimum distortion can be found in time 5n+o(n). This is the first algorithm breaking the trivial n!-barrier.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| ID Code: | 123466 |
| Deposited On: | 20 Sep 2021 09:00 |
| Last Modified: | 20 Sep 2021 09:00 |
Repository Staff Only: item control page
